BZOJ2600_ricehub

题目传送门

这道题一开始我还以为是贪心，sort一遍直接取中点然后求最优值。

但写了之后才发现错误，设置的谷仓只要是一段区间的中点即可。这段区间的两端一定是两片谷田。

所以枚举区间的左端点，二分右端点，但问题是如何O(1)判断？

设sumi表示1~i点的和。

L~R区间所需要的费用分成两段来求。

一段为L~mid-1，一段为mid+1~R。

L~mid-1=a[mid]*(mid-l)-(sum[k-1]-sum[l-1]);

mid+1~R=sum[r]-sum[k]-a[k]*(r-k);

两者相加即为这段区间的费用总和。

code：

#include <cstdio>

#include <algorithm>

using namespace std;

int read()

{

    char c;while(c=getchar(),c<''||c>'');int x=c-'';

    while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x;

}

int abs(int x){return x>?x:-x;}

const int MAXN=;

int R,L,a[MAXN],i,ans;

long long B,sum[MAXN];

int find(int l,int r)

{

    long long w=,k=l+r+>>;

    w=a[k]*(k-l)-(sum[k-]-sum[l-])+sum[r]-sum[k]-a[k]*(r-k);

    return w<=B;

}

int check(int x)

{

    int l=x,r=R,mid,tot;

        while(l<=r){

            mid=l+r>>;

            if(find(x,mid))l=mid+,tot=mid;

            else r=mid-;

        }

    return tot-x+;

}

int main()

{

//    freopen("x.txt","r",stdin);

    R=read(),L=read();scanf("%lld",&B);

        for(i=;i<=R;i++)a[i]=read(),sum[i]=sum[i-]+a[i];

        for(i=;i<=R;i++){

            ans=max(ans,check(i));

        }

    printf("%d",ans);

    return ;

}

巴特西

BZOJ2600_ricehub_KEY

最新文章

热门文章