CF1700D

dottle · 2022-05-05 21:47:46 · 题解

思路

看起来答案好像是 \lceil \frac {\sum v}{t} \rceil 。但其实这样不一定够，因为有可能前面的槽还没填满，后面的槽就已经开始漏水了！一个简单的例子：v_1=10,v_2=1。这样 t< 10 的时候是无解的！思考一下出现这个现象的原因：前 i 个水槽有 \sum_{j=1}^i v_i 的容积，又只能由前 i 个水龙头提供水。也就是说，前 i 个水槽至少需要 \lceil \frac {\sum_{j=1}^i v_i}{i} \rceil 秒才能填满。求出这 n 个值的最大值，我们就可以得到一个 t 的下界了，不妨设为 X。如果输入的 t 小于 X，则肯定无解。

在进行了上面的思考后，容易产生一个误解，即会漏很多水出去。其实不会，因为我们开水龙头的时候，肯定是先开第一个，再开第二个，这样依次开下去。然后可以这样想，我们把第一个水龙头开完 t 秒后，再开第二个。这样看来每一个时刻水填充的肯定都是一个前缀。直到最后发现所有槽都被填完后，就不会再开水龙头了。这样看来，就只有开最后一个水龙头的时候会浪费一些水，所以答案其实就是 \lceil \frac {\sum v}{t} \rceil 。

题解

设 X=\max_i \lceil \frac {\sum_{j=1}^i v_i}{i} \rceil，则：

• 若 t<X，无解;
• 否则，答案为 \lceil \frac {\sum v}{t} \rceil 。

代码

#include<bits/stdc++.h>
#define int long long
const int N=1005000;
using namespace std;

int n,q,a[N];
int res;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=n;i++)res=max(res,(a[i]+i-1)/i);
    cin>>q;
    for(int i=1;i<=q;i++){
        int x;cin>>x;
        cout<<(x<res?-1:(a[n]+x-1)/x)<<'\n';
    }
}

main(){
    ios::sync_with_stdio(0);
    solve();
}