[cf] 763 div2 C. Balanced Stone Heaps

前言

t a g : tag : tag: 二分答案 贪心 check *1600 传送门 :

题意 : 给定一个数组 a [ ] a[] a[] ,询问执行多次操作之后,最小的最大值是多少

操作定义如下 : 选中 i , i ∈ [ 2 , N ] i,i \in[2,N] i,i∈[2,N],确立一个值 d d d, a [ i ] − 3 ∗ d , a [ i − 1 ] + d , a [ i − 2 ] + 2 ∗ d a[i]-3*d,a[i-1]+d,a[i-2]+2*d a[i]−3∗d,a[i−1]+d,a[i−2]+2∗d

思路 : 因为题目中含有 最大的最小,我们考虑二分出最小的答案

对于 c h e c k check check部分,显然我们需要从后往前作一次贪心

我们设 d [ i ] d[i] d[i]表示原始的 a [ i ] a[i] a[i],用 p r e [ i ] pre[i] pre[i]表示增加的量

因此对于每一个 i i i的合法,当且仅当 d [ i ] + p r e [ i ] > = x d[i]+pre[i]>=x d[i]+pre[i]>=x

同时我们有需要保证前面的尽可能大,所以我们对 t m p = m i n ( d [ i ] + p r e [ i ] − x , d [ i ] ) tmp=min(d[i]+pre[i]-x,d[i]) tmp=min(d[i]+pre[i]−x,d[i]) 这样子即保证了当前的合法,又保证了前面的值能尽可能大

code :

int d[N],a[N];
int pre[N];
int n;

bool check(int x){
	
	for(int i=1;i=3 ; i-- ){
		
		if(d[i] + pre[i] >=  x){ //满足条件
			//贪心的进行分配 计算可以分配的差值
			int tmp = d[i] + pre[i] - x ;
			
			tmp = min(tmp,d[i]);
			//保证前面尽可能大
			tmp /=3;
			
			pre[i-1] += tmp;//可以分配的
			pre[i-2] += tmp*2;
			
		}else return false;
	}
	
	if(d[2] + pre[2] n;
	
	int l = 0 ,r = 0 ;
	
	for(int i=1;i>a[i];
		r = max(r,a[i]);
	}
	
	while(l>1;
		if(check(mid)) l = mid+1;
		else r = mid-1;
	}
	
	cout