CF1700D题解

happy_dengziyue · 2022-06-21 19:59:11 · 题解

1 视频题解

2 思路

设 s[i]=\sum_{j=1}^iv[j]。

我们可以发现，就算是打开全部的管道，将第一个装完也要 s[1] 秒，将第二个装完也要 \lceil\dfrac{s[2]}{2}\rceil，依次类推，将第 i 个装完也要 \lceil\dfrac{s[i]}{i}\rceil 秒。

所以，计算出打开全部管道需要多少秒钟装完水，不满足此条件的直接输出 -1 即可。

然后我们发现，尽可能打开上游的管道是最好的。并且，在不输出 -1 的情况下，装满水一定需要且只需要 \lceil\dfrac{s[n]}{t}\rceil 个管道。

输出即可。

3 代码与记录

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define max_n 200000
#define inf 2e15
int n;
int q;
long long a[max_n+2];
long long s[max_n+2];
long long need;//最少需要时间
int ans;
long long divll(long long x,long long y){
    return (x+y-1)/y;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("CF1700D_1.in","r",stdin);
    freopen("CF1700D_1.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lld",a+i);
    s[0]=0;
    for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i];
    need=a[1];
    for(int i=2;i<=n;++i)need=max(need,divll(s[i],i));
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        long long x;
        scanf("%lld",&x);
        if(x<need)printf("-1\n");
        else printf("%lld\n",divll(s[n],x));
    }
    return 0;
}

记录传送门

By dengziyue