BZOJ2600: [Ioi2011]ricehub

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2600

Solution

大意：一条路上给定n个稻田，要求建一个粮仓，并选出若干个稻田，要求这些稻田到粮仓的距离之和不超过B，问最多能选多少稻田。
显然粮仓应该建在中位数的位置，搞一个队列，右指针从左往右扫，如果当前队列里的距离之和超过了B，左指针往右移；否则更新答案。距离之和可以搞一个前缀和O(1)求。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 100005
using namespace std;
inline ll read(){
    char ch; ch=getchar(); ll f=1,x=0;
    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;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
ll a[N],sum[N],n,B,ans;
bool judge(ll l,ll r){
    ll mid=l+((r-l+1)>>1);
    ll sum1=(mid-l)*a[mid]-sum[mid]+sum[l];
    ll sum2=sum[r]-sum[mid]-(r-mid)*a[mid];
    return sum1+sum2>B;
}
int main(){
    n=read(); B=read(); B=read();
    for (ll i=1;i<=n;i++)
        sum[i]=sum[i-1]+(a[i]=read());
    for (ll i=1,j=0;i<=n;i++){
        while (judge(j,i)) j++;
        ans=max(ans,i-j);
    }
    write(ans);
}