题解 CF954G 【Castle Defense】

VenusM1nT

2020-11-06 08:19:20

Solution

非常清真的二分答案。 ![](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; } ```