CodeForces - 460C（二分+差分）

佚名 5年前 (2019-12-09) 算法 771人围观抢沙发百度已收录

题意

https://vjudge.net/problem/CodeForces-460C

一个长度为 n 的序列 a ，你有 m 次操作的机会，每次操作是将其中连续的 w 个元素增加 1 。最大化最终序列的最小值。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路

最大化最小值，二分的套路题。

数据范围1e5，所以我们要O（n）check。

如何能做到O（n）?

差分！

求出查分数组后，差分的前缀和就是原数组，如果我们要check(x)，那么每当前缀和<x时，就要c[i]+=(x-s)，c[i+w]-=(x-s)，因为可以连续给w个元素加1，所以在i+w的地方减去相应值，这样可以最大化利用这个w，最后我们判断累计的x-s是否小于等于m即可。

注意每次二分后要还原差分数组！！

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll inv(ll a,ll p){return qpow(a,p-2);}
ll read()
{
    ll x=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x;
}
int n,m,w;
ll a[N],c[N];
bool check(ll x)
{
    ll sum=0,res=0;
    for(int i=1;i<=n;i++)
    {
        sum+=c[i];
        if(sum<x)
        {
            res+=x-sum;
            c[i]+=(x-sum);
            if(i+w<=n)
                c[i+w]-=(x-sum);
            sum=x;
        }
    }
    for(int i=1;i<=n;i++)
        c[i]=a[i]-a[i-1];
    return res<=m;
}
int main()
{
    std::ios::sync_with_stdio(false);
    n=read(),m=read(),w=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        c[i]=a[i]-a[i-1];
    }
    ll l=1,r=1e14,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else
            r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}