[数据结构与算法][cf] 802 Div. 2 D - River Locks

前言

$tag:$ 贪心 公式推导 教练 : 图佬

传送门 :

题意 :

给定$n$个体积$v_i$的水渠,每个水渠上面都有水管

现在有$q$个询问

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

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

思路 :

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

$开闸数\ge \frac{总蓄水数}{时间}$

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

那么什么时候才 不合法呢

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

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

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

因此我们所需要的$时间T=max(T,\frac{su{m}_i}{i})$

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

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<<endl;
		else cout<<(sum + x - 1)/x<<endl;
	}
}