【菜笔cf刷题日常-1600】C. Balanced Stone Heaps（二分求min/max）

链接：https://codeforces.com/problemset/problem/1062/D

题意：给你一个序列，从 i = 3 开始到 i = n 进行操作，每一次操作可以将 a[ i ] 减去 3 * d（d对于每一次操作都是任意的），使得a[ i - 1 ]增加 d 、a[ i - 2 ]增加 2 * d。问在选取每次操作的 d 后，最终结果中 序列最小值 的 最大值 是多少？

思路：求 最小值 的 最大值 ，首先想到用二分解决。直接枚举答案，判断方法从尾向前遍历，每次判断此时其本身值与经过操作获得的值的和，若小于答案则答案不成立；否则尽可能多地取出其本身的值用以操作分配后前面的数。最终单独判断 a[ 1 ] 、a[ 2 ] 的情况。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t,k,l,r,q,p,x,idx,res,cnt,sum,flag,maxx,minn;
const int N=200010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
int a[N],b[N];

bool check(int mid) {

	for(int i=0; i<=n; i++)b[i]=0;
	for(int i=n; i>=3; i--) {
		if(a[i]+b[i]<mid)return 0;
		
		int tem=min(a[i]-mid+b[i],a[i]);
		b[i-2]+=tem/3*2;
		b[i-1]+=tem/3;
	}
	if(a[1]+b[1]<mid || a[2]+b[2]<mid)return 0;
	return 1;
}

void solve(){
	cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>a[i];
		}

		l=-1,r=1e9+10;
		while(l+1<r) {
			int mid=(l+r)/2;
			if(check(mid))l=mid;
			else r=mid;

		}
		cout<<l<<'\n';

}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)solve();
	return 0;
}