【CF1119E】Pavel and Triangles

题目大意：有 N 种长度的边，第 i 种长度为 \(2^i\)，给定一些数量的这些边，问最多可以组合出多少种三角形。

题解：应该是用贪心求解，不过选择什么样的贪心策略很关键。

首先分析可知，两个较大边和一个较小边可以组合出三角形，但是反过来不行。从后往前考虑，记录到目前为止有多少对边，若当前边为奇数，考虑是否有足够的对来匹配，若没有，则一定失配，最后计算答案即可。

代码如下

#include <bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()

#define cls(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int dx[]={0,1,0,-1};

const int dy[]={1,0,-1,0};

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const double eps=1e-6;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll sqr(ll x){return x*x;}

inline ll fpow(ll a,ll b,ll c){ll ret=1%c;for(;b;b>>=1,a=a*a%c)if(b&1)ret=ret*a%c;return ret;}

inline ll read(){

    ll x=0,f=1;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

    return f*x;

}

/*------------------------------------------------------------*/

const int maxn=3e5+10;

int n;

ll a[maxn];

void read_and_parse(){

    n=read();

    for(int i=1;i<=n;i++)a[i]=read();

}

void solve(){

    ll ans=0,p=0;

    for(int i=n;i>=1;i--){

        p+=a[i]/2;

        if(a[i]%2==1&&p>0)--p,++ans;

    }

    ans+=p/3*2;

    if(p%3==2)++ans;

    printf("%lld\n",ans);

}

int main(){

    read_and_parse();

    solve();

    return 0;

}