Codeforces Round #763 (Div. 2) C. Balanced Stone Heaps（弱鸡分析）

Codeforces Round #763 (Div. 2) C. Balanced Stone Heaps（弱鸡分析）

题目链接

思路

正解是二分答案+贪心，很多人可能不明白为何检验的时候能从后往前检验，这里来分析一波。对于每次二分枚举到的最小值 x x x , 我们要保证每一堆石头的数量最后都 ≥ x geq x ≥x ，如果从前往后分配，对于当前堆的石头数量 a i a_i ai​ , 我们无法知道该分配多少给 a i − 1 , a i − 2 a_{i-1}, a_{i-2} ai−1​,ai−2​ ，也无法知道分配了 a i a_i ai​以后能不能再让 a i ≥ x a_i geq x ai​≥x。如果从后往前, 如果当前 b i ≤ x b_i leq x bi​≤x, 那么这次二分不合法， 否则我们在 ( b i − x ) 3 frac {(b_i -x )}{3} 3(bi​−x)​ 和 a i 3 frac {a_i}{3} 3ai​​之间取一个最小值分配给 b i − 1 b_{i-1} bi−1​ 和 b i − 2 {b_{i-2}} bi−2​，肯定不能小于 a i 3 frac {a_i}{3} 3ai​​，不然你拿什么分配给前面的。最后再判断 b 1 b_1 b1​ 和 b 2 b_2 b2​满足条件与否即可。

AC代码

#include
#define ll long long
#define rep(i,x,y) for(int i=x; i<=y; i++)
#define per(i,x,y) for(int i=x; i>=y; i--)
using namespace std;
const int N = 2e5+9;
ll  a[N],b[N];
int n;
bool check(ll x){
	rep(i,1,n) b[i]=a[i];
	per(i,n,3){
		if(b[i]=x&&b[2]>=x;
}
int main(){
	
	int t;
	cin>>t;
	while(t--){

	 scanf("%d",&n);
	 rep(i,1,n) scanf("%d",a+i);
	 ll l=1,r=1e18;
	 ll ans=0;
	 while(l<=r){
	 	ll mid = (l+r)>>1;
	 	if(check(mid)) {
	 		ans=mid;
	 		l=mid+1;
		 }
		 else r=mid-1;
	 }
	 printf("%lldn",ans);
	}
	
	return 0;
}