Codeforces Round ＃802 (Div. 2) C D

Portal ：
C. Helping the Nature

D. River Locks

C The question ： Give you a sequence a, You can use the following three operations ：
Operation 1 ： For interval [1,i] - 1

Operation two ： For interval [i,n] - 1

Operation three ： For interval [1,n] + 1

Find the minimum number of operations so that a The sequence is all 0.

C analysis ： Observe the nature of the operation ：
Operation 1 ： Make the difference d[i+1]+1

Operation two ： Make the difference d[i]-1

Operation three ： Operation three

O(n) After paving （ All the numbers are the same ） Plus a Just one number of the sequence .

C Code ：
 

#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 The question ： Yes n A reservoir , The capacity of each reservoir is v[i], And there is a water pipe connection , After the water pipe is opened, it will flow into 1 Liters of water . Note that each reservoir is also connected to the next reservoir , When the first i When the reservoir is full , The overflowing water will flow to i+1 In a reservoir .

You need to answer q Queries , Give time each time t, At least how many water pipes can be opened to make all reservoirs in t Filled in time .

D analysis ： Set on x A water pipe , Then the best way to open the water pipe must be the front x individual . Consider dichotomy check(x,t) open x Can a pipeline t Fill it up in seconds , Obviously, it can only support O(1) The judgment of the , Fill up x It is easy to calculate the time required for the reservoir behind , But it is necessary to ensure that the reservoir in front is full . Prepare for it , set up dp[i] It means before opening i Before the pipes are filled i The time required for a reservoir , Sure O(n) solve .

D Code ：

#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];// Before opening i Before the pipes are filled i The time required for a reservoir 
int n;

int check(int x,int t)// open x Can a pipeline t Fill it up in seconds 
{
    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();
}