题意
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;
}