https://www.luogu.com.cn/problem/CF460C
二分答案+差分
#include<bits/stdc++.h>
using namespace std;
long long n,m,w,a[1000000],l=0,r=1e10,sum[1000000],aa[1000000];
int check(long long x)//注意数据范围
{
long long ans=0;
memset(sum,0,sizeof(sum));
memset(aa,0,sizeof(aa));
for(int i=1;i<=n;i++) aa[i]=min((long long)0,a[i]-x);
for(int i=1;i<=n;i++)
{
sum[i]+=sum[i-1];
long long k=sum[i]+aa[i];//当前的数加上差分前缀和后与x差多少
if(k<0)
{
sum[i]-=k;
ans-=k;
sum[i+w]+=k;//注意i+w边界
}
if(ans>m) return 0;
}
return 1;
}
int main()
{
cin>>n>>m>>w;
for(int i=1;i<=n;i++) cin>>a[i];
while(l<r-1)
{
long long mid=(l+r)>>1;
if(check(mid)) l=mid;
else r=mid;
}
if(check(r)) cout<<r;
else cout<<l;
return 0;
}```