题意

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

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

思路

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

数据范围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;

}

巴特西

CodeForces - 460C（二分+差分）

题意

思路

代码

最新文章

热门文章