比较裸的二分,但是比赛的时候脑抽,用树状数组瞎搞过了,但是边界条件没注意让hack了。
后来看到有人写了很简单的版本,又过了一遍,提醒一下自己不能忘记基本算法。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int a[100005],b[100005],sum[100005];
int n,m,k;
bool judge(int mid)
{
int step=m,add=0;
memset(sum,0,sizeof(sum));
for(int i=0;i<n;i++)
b[i]=a[i];
for(int i=0;i<n;i++)
{
add+=sum[i];
b[i]+=add;
if(b[i]<mid)
{
int temp=mid-b[i];
b[i]=mid;
step-=temp;
add+=temp;
sum[min(i+k,n)]-=temp;
if(step<0)
return false;
}
}
return true;
}
int main()
{
while(cin>>n>>m>>k)
{
int minn=1e9;
int maxx=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
minn=min(minn,a[i]);
maxx=max(maxx,a[i]);
}
int low=minn,high=m+maxx;
int ans=minn;
while(low<=high)
{
int mid=(low+high)>>1;
if(judge(mid))
{
ans=max(ans,mid);
low=mid+1;
}
else
high=mid-1;
}
cout<<ans<<endl;
}
}