Codeforces Round ＃802 (Div. 2) C D

传送门：
C. Helping the Nature

D. River Locks

C题意：给你一个序列a，你可以使用以下三个操作：
操作一：对于区间[1,i] - 1

操作二：对于区间[i,n] - 1

操作三：对于区间[1,n] + 1

求最小操作次数使得a序列全为0。

C分析：观察操作的本质：
操作一：使得差分d[i+1]+1

操作二：使得差分d[i]-1

操作三：操作三

O(n)铺平之后（所有数字都一样了）再加上a序列的一个数字即可。

C代码：
 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int a[maxn],d[maxn];

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        d[i]=a[i]-a[i-1];
    }
    int cnt=0;
    int a1=a[1];
    for(int i=2;i<=n;i++)
    {
        cnt+=abs(d[i]);
        if(d[i]<0)
        {
            a1+=d[i];
        }
    }
    cnt+=abs(a1);
    cout<<cnt<<endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}

---

D题意：有n个水库，每个水库的容量为v[i]，且有一个水管连接，水管打开后每秒会流入1升的水。注意每个水库还连接着下一个水库，当第i个水库满了之后，溢出的水会流到第i+1个水库中。

你需要回答q次查询，每次给出时间t，求至少打开多少个水管才能使得所有水库在t时间内被灌满。

D分析：设打开x个水管，那么使得打开的水管最优必须是前面x个。考虑二分check(x,t) 开x个管道能否t秒灌满，显然只能支持O(1)的判断，灌满x后面的水库所需的时间好算，但需要保证前面的水库灌满。预处理一下，设dp[i]表示开前i个管道并灌满前i个水库所需的时间，可以O(n)解决。

D代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int a[maxn],sum[maxn];
int dp[maxn],ot[maxn];//开前i个管道并灌满前i个水库所需的时间
int n;

int check(int x,int t)//开x个管道能否t秒灌满
{
    int rem=max(sum[n]-sum[x]-ot[x],0ll);
    int tt=(rem+x-1)/x;
    if(tt+dp[x]<=t) return 1;
    return 0;
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    for(int i=1;i<=n;i++)
    {
        int t=max((a[i]-dp[i-1]-ot[i-1]+i-1)/i,0ll);
        dp[i]=dp[i-1]+t;
        ot[i]=dp[i]*i-sum[i];
    }

    int q;
    cin>>q;
    while(q--)
    {
        int t;
        cin>>t;
        int l=1,r=n,ans=-1;
        while(l<=r)
        {
            int m=l+r>>1;
            if(check(m,t))
            {
                r=m-1;
                ans=m;
            }
            else l=m+1;
        }
        cout<<ans<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    int t=1;
    // cin>>t;
    while(t--) solve();
}