没错是双倍经验。
题意：
一个长度为 \(n\) 的序列 \(a\) ，你有 \(m\) 次操作的机会，每次操作是将其中连续的 \(w\) 个元素增加 \(1\) 。最大化最终序列的最小值。
\(1 \leq w \leq n \leq 1e5 /5e5,1 \leq m \leq 1e5\)
解题思路：
令最小值最大，不难想到二分答案。
但是不知道check函数怎么写。
考虑贪心，假如二分到一个值为 \(mid\)，从左往右扫，遇到某个值 \(x\) ，位置为 \(p\)，如果 \(x <mid\)，那么就对 \([p,p+w-1]\) 进行 \(mid-x\) 次操作，假如 \(p+w-1>n\) ，就直接对 \([n-w+1,n]\) 进行操作即可。最后判断操作数 \(res\) 是否小于等于 \(m\) 。
由于小于 \(mid\) 的值无论要被加到等于 \(mid\)，在使该位置为左端点的情况下，左边所有的值已经大于等于 \(mid\)，因此往右加才会使操作数尽可能地少，并不存在浪费操作数这一说。
想到二分答案之后自己确实也考虑过这一点，又习惯性地觉得这样做的话不行，觉得这个贪心是假的，可是自己也不会证。颓了题解发现就是这么做的，感觉自己就是个神必。果然自己还是不会贪心。
维护覆盖操作的话线段树或差分数组均可。使用线段树的复杂度是 \(O(n\log ^2n)\) （显然无法通过 \(5e5\)），差分数组的话是 \(O(n\log n)\) 。
代码：
#include <cstdio>
#include <algorithm>
#define Reg register
#define int long long
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int maxn=101000,inf=2147483100;
int n,m,K,a[maxn],minn=inf,maxx=0;
//现在应该比较确定的是要二分答案
//但他妈该怎么写
//好题解是二分
//我是神必
struct EE{
int l,r,v,lz;
}tr[maxn<<2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void build(int rt,int l,int r){
tr[rt].l=l;
tr[rt].r=r;
tr[rt].lz=0;
if(l==r) return tr[rt].v=a[l],void();
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
}
inline void pushdown(int rt){
if(tr[rt].lz){
tr[lson].lz+=tr[rt].lz;
tr[rson].lz+=tr[rt].lz;
tr[rt].lz=0;
}
}
inline void update(int rt,int l,int r,int v){
if(l<=tr[rt].l&&tr[rt].r<=r){
tr[rt].lz+=v;
return;
}
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(l<=mid) update(lson,l,r,v);
if(r>mid) update(rson,l,r,v);
}
inline int query(int rt,int p){
if(tr[rt].l==tr[rt].r){
tr[rt].v+=tr[rt].lz;
tr[rt].lz=0;
return tr[rt].v;
}
pushdown(rt);
int mid=(tr[rt].l+tr[rt].r)>>1;
if(p<=mid) return query(lson,p);
else return query(rson,p);
}
inline bool check(int mid){
int res=0;
build(1,1,n);
for(Reg int i=1;i<=n;++i){
int p=query(1,i);
if(p>mid) continue;
res+=mid-p;
if(i<=n-K+1) update(1,i,i+K-1,mid-p);
else update(1,n-K+1,n,mid-p);
if(res>m) return 0;
}
return 1;
}
signed main(){
n=read(),m=read(),K=read();
for(Reg int i=1;i<=n;++i){
a[i]=read();
minn=min(minn,a[i]);
maxx=max(maxx,a[i]);
}
int l=minn,r=inf,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}