题解：CF1119E Pavel and Triangles

· · 题解

题目传送门：CF1119E Pavel and Triangles

Solution：

由于边长都为 2 的幂，因为 2^{k-1}+2^{k-1} 不大于 2^k，所以一条长边加上两条短边是无法组成三角形，只能是两条长边加一条短边、三条长边组成三角形。

所以我们从小到大进行考虑。

我们开一个变量 sum 记录短边数量。

对于每一条长度的边数量 cnt，如果这些边的数量除以 2 大于等于短边数量，也就是两条长边加上一条短边短边不够，那么就加入三条长边情况。

我们就直接在答案上加上这些长度边的数量加上短边数量的和除以三。

也就是：(cnt+sum)\div 3。

短边数量就会变成 (cnt+sum)\bmod3。

反之如果短边的数量大于边的数量除以 2，那么我们只能构造两条长边加一条短边的情况，我们就直接在答案上加上边的数量除以 2。

也就是：cnt\div 2。

短边数量减去 cnt\div 2-cnt\bmod2。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[300010];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,ans=0,cnt=0;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        if(a[i]/2>ans)cnt+=(a[i]+ans)/3,ans=(a[i]+ans)%3;
        else cnt+=a[i]/2,ans-=a[i]/2,ans+=a[i]%2;
    } cout<<cnt<<'\n';
    return 0;
}

完结撒花。