题解 CF954G 【Castle Defense】
VenusM1nT
2020-11-06 08:19:20
非常清真的二分答案。
![](https://t1.picb.cc/uploads/2020/10/26/tYAt1r.png)
看到“最小值的最大值”,考虑二分答案 $\text{mid}$。记 $a_i$ 为每个点的权值,考虑对于每个 $a_i<\text{mid}$ 贪心,对于当前点,它前面的点全部已经满足条件,那么这个区间肯定越右边越优,于是对 $[i-r,i+r]$ 这个区间的权值 $+(\text{mid}-a_i)$,最后判断 $k$ 个 archer 还有没有得剩就可以了。
![](https://t1.picb.cc/uploads/2020/10/26/tY898y.png)
```cpp
#include<bits/stdc++.h>
#define N 500000
#define reg register
#define inl inline
#define int long long
using namespace std;
int n,r,k,sum[N+5],a[N+5],c[N+5];
inl bool Check(reg int mid)
{
memcpy(c,a,sizeof(a));
reg int x=k;
for(reg int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+c[i];
if(sum[i]<mid)
{
reg int y=mid-sum[i];
c[i]+=y;
c[min(i+r*2+1,n+1)]-=y;
x-=y;
sum[i]+=y;
if(x<0) return 0;
}
}
return 1;
}
signed main()
{
scanf("%lld %lld %lld",&n,&r,&k);
for(reg int i=1;i<=n;i++)
{
reg int x;
scanf("%lld",&x);
a[max(i-r,1ll)]+=x;
a[min(i+r+1,n+1)]-=x;
}
reg int l=0,r=1ll<<62,ans;
while(l<=r)
{
reg int mid=(l+r)>>1;
if(Check(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
```