Codeforces460C【二分+线段树】

二分最小值，如果你能实现这个最小值是可以实现的，那么一定是最优的，因为每次区间+1，原来存在的最小值的个数还是存在的，但是新的可能会多起来，所以最小值递增还是最优到最优的；考虑如果不能实现这个最小值，那么他一定是比之前这个值少的，因为最小值不变，而且个数变少；区间维护可以线段树。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=1e5+10;
struct SegT{
int sum;
int val;
int left;
int right;
};

SegT q[N*4];
char id[N];
int n,m,w;
int a[N];

void Build(int num,int L ,int R)
{
q[num].left=L;
q[num].right=R;
q[num].val=0;
if(L==R)
    {
q[num].sum=a[L];
return;
    }
int mid=(L+R)>>1;
    Build(2*num,L,mid);
    Build(2*num+1,mid+1,R);
q[num].sum=q[2*num].sum+q[2*num+1].sum;
}

void PushDown(int num)
{
if(q[num].val)
    {
q[2*num].sum+=(q[2*num].right - q[2*num].left+1)*q[num].val;
q[2*num].val+=q[num].val;
q[2*num+1].sum+=(q[2*num+1].right - q[2*num+1].left+1)*q[num].val;
q[2*num+1].val+=q[num].val;
q[num].val=0;
    }
}

void Update(int num,int s,int t,int v)
{
if(q[num].left>=s&&q[num].right<=t)
    {
q[num].sum+=(q[num].right - q[num].left+1)*v;
q[num].val+=v;
return;
    }
    PushDown(num);
int mid=(q[num].left+q[num].right)>>1;
if(mid>=t)
        Update(2*num,s,t,v);
else if(mid<s)
        Update(2*num+1,s,t,v);
else
    {
        Update(2*num,s,mid,v);
        Update(2*num+1,mid+1,t,v);
    }
q[num].sum=q[2*num].sum+q[2*num+1].sum;
}

int query(int num,int x)
{
if(q[num].left==q[num].right&&q[num].left==x)
return q[num].sum;
    PushDown(num);

int mid=(q[num].left+q[num].right)>>1;

if(mid>=x)
return query(2*num,x);
else
return query(2*num+1,x);
}

bool Judge(int k)
{
int ti=0;
int tmp,x;
    Build(1,1,n);
for(int i=n;i>=1;i--)
    {
        tmp=query(1,i);
if(tmp>=k) continue;
x=k-tmp;
if(i>=w)
        {
            Update(1,i-w+1,i,x);
            ti+=x;
        }
else
        {
            Update(1,1,i,x);
            ti+=x;
        }
if(ti>m) return false;
    }
return true;
}

int main()
{
    scanf("%d%d%d",&n,&m,&w);
int tmax=1,tmin=2e9;
for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmax=max(tmax,a[i]);
        tmin=min(tmin,a[i]);
    }
int Left=tmin,Right=tmax+m;
while(Left<Right)
    {
int mid=Left+(Right-Left+1)/2;
if(Judge(mid))
            Left=mid;
else
            Right=mid-1;
    }
printf("%d\n",Left);
return 0;
}