[CodeForces954G]Castle Defense（二分答案+差分）-白红宇

[CodeForces954G]Castle Defense（二分答案+差分）

阅读量：6824 次

发布时间：2019-06-26

本文共 996 字，大约阅读时间需要 3 分钟。

Description

Solution

二分答案，套一个差分标记即可

每次放弓箭手显然越右边越优

Code

#include 
    
     #include 
     
      #include 
      
       #define N 2000010#define ll long longusing namespace std;int n,R;ll A[N],k,Ans,l=1e18,r=1e20,cf[N],sum[N];inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}bool check(ll m){    ll tmp=k,x=0;    memset(cf,0,sizeof(cf));    for(int i=1;i<=n;++i){        x+=cf[i];        if(sum[min(i+R,n)]-sum[max(i-R-1,0)]+x
       
        tmp) return 0;            tmp-=d;            x+=d;            cf[i+2*R+1]-=d;        }    }    return 1;}int main(){    scanf("%d%d%I64d\n",&n,&R,&k);    for(int i=1;i<=n;++i){sum[i]=sum[i-1]+(A[i]=read());l=min(l,A[i]);}    while(l
        
         >1ll;        if(check(m)) Ans=m,l=m+1;        else r=m;    }    printf("%I64d\n",Ans);    return 0;}