[cf] 802 Div. 2 D - River Locks

t a g : tag : tag: 贪心 公式推导 教练 : 图佬

传送门 :

题意 :

给定 n n n个体积 v i v_i vi​的水渠,每个水渠上面都有水管

现在有 q q q个询问

对于每个询问,最少的开水管数使得能在 t j t_j tj​秒内填满所有水渠

(显然如果一个水渠满了会流到下一个水渠里面)

思路 :

开 闸 数 × 时 间 ≥ 总 蓄 水 数 开闸数 × 时间 ge 总蓄水数 开闸数×时间≥总蓄水数 , 显然可以使得总方案成立

开 闸 数 ≥ 总 蓄 水 数 时 间 开闸数 ge frac{总蓄水数}{时间} 开闸数≥时间总蓄水数​

同时又因为需要 最小, 所以 开 闸 数 = 总 蓄 水 数 时 间 开闸数 = frac{总蓄水数}{时间} 开闸数=时间总蓄水数​

那么什么时候才 不合法呢

时间 , 当且仅当最大的时间花费 不能满足的时候 是 不合法的

根据上面的公式 时 间 ≥ 总 蓄 水 数 开 闸 数 时间 ge frac{总蓄水数}{开闸数} 时间≥开闸数总蓄水数​

因为每个水满了都是会往下一个流,我们贪心的考虑尽可能开前面的水闸,使得后面的尽可能是被多余的水流过填满的

因此我们所需要的 时 间 T = m a x ( T , s u m i i ) 时间T = max( T,frac{sum_i}{i}) 时间T=max(T,isumi​​)

如果你能看懂这篇题解那都说明是 图佬教的好❤

code :

int a[N],n;

void solve(){
	cin>>n;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	
	ll maxn = -1e18;
	
	
	ll sum = 0 ;
	
	for(int i=1;i<=n;i++){
		sum = sum+a[i];
		maxn = max(maxn,(sum + i - 1 )/i );
	}
	
	int q;cin>>q;
	while(q -- ){
		int x;cin>>x;
		if(x < maxn) cout<<-1<