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

文章目录

R e s u l t Result Result

---

H y p e r l i n k Hyperlink Hyperlink

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

---

D e s c r i p t i o n Description Description

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

问用这些木棍最多能同时拼出多少个三角形
数据范围： n ≤ 3 × 1 0 5 , a i ≤ 1 0 9 n\leq 3\times 10^5,a_i\leq 10^9 n≤3×105,ai​≤109

---

S o l u t i o n Solution Solution

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

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

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

---

C o d e Code 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);
}