2020年12月3日提高组 C 毛毛的三角

$Result$

$Hyperlink$

https://www.luogu.com.cn/problem/U142634

$Description$

有$n$种木棍，第$i$种木棍的长度为$2^{i-1}$，它有$a_i$根

问用这些木棍最多能同时拼出多少个三角形
数据范围：$n\le 3\times 10^5,a_i\le 10^9$

$Solution$

显然一个三角形三边长必然是$(2^i,2^j,2^j)i\le j$的形式
显然大部分情况下1,2,2的情况是最优的，当然也有可能是1,1,1这种情况
贪心的先考虑前者，再考虑后者就好了

具体地，$canpp$表示现在可以(1,2,2)匹配的数量，$need$表示前面需要匹配的
假设第$i$种木棍有$x$根，那么$canpp=min(\lfloor \frac{x}{2}\rfloor ,need)$，然后去匹配，接着看如果木棍有剩余，不小于三根的话让其自我匹配就好了

时间复杂度：$O(n)$

$Code$

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 300010
using namespace std;int n,x,need,canpp;
LL res;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();for(register int i=1;i<=n;i++) {x=read();canpp=min(x/2,need);need-=canpp;res+=canpp;x-=canpp*2;res+=x/3;need+=x%3;}printf("%lld",res);
}