BZOJ_2600_[Ioi2011]ricehub

BZOJ_2600_[Ioi2011]ricehub_二分答案

Description

乡间有一条笔直而长的路称为“米道”。沿着这条米道上 R 块稻田，每块稻田的坐标均
为一个 1 到 L 之间(含 1 和 L)的整数。这些稻田按照坐标以不减的顺序给出，即对于 0 ≤ i <
R，稻田 i 的坐标 X[i]满足 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L。
注意：可能有多块稻田位于同一个坐标上。
我们计划建造一个米仓用于储存尽可能多的稻米。和稻田一样，米仓将建在米道上，其
坐标也是一个 1 到 L 之间的整数（含 1 和 L）。这个米仓可以建在满足上述条件的任一个位
置上，包括那些原来已有一个或多个稻田存在的位置。
在收获季节，每一块稻田刚好出产一滿货车的稻米。为了将这些稻米运到米仓，需要雇
用一位货车司机来运米。司机的收费是每一满货车运送一个单位的距离收取 1 元。換言之，
将稻米从特定的稻田运到米仓的费用在数值上等于稻田坐标与米仓坐标之差的绝对值。
不幸的是，今年预算有限，我们至多只能花费 B 元运费。你的任务是要帮我们找出一个
建造米仓的位置，可以收集到尽可能多的稻米。

Input

第一行三个整数 R L B
接下来R行每行一个整数表示X[i]

Output

一个整数最多稻米数

Sample Input

5 20 6
1
2
10
12
14

Sample Output

3
HINT
1 ≤ R ≤ 100,000
1 ≤ L ≤ 1,000,000,000
0 ≤ B ≤ 2,000,000,000,000,000

可以发现选择的稻米位置是一段连续的区间。

二分答案$x$，转化为判断是否有长度为$x$的区间可以选。

并且建造米仓的位置一定是中位数最优，做个前缀和就可以$O(1)$求出花费。

每次$check$是$O(n)$的，总时间复杂度$O(nlogn)$。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
#define N 100050
int n,L,a[N];
ll s[N],B;
ll solve(int l,int r) {
    int mid=(l+r)>>1;
    return 1ll*a[mid]*(mid-l+1)-(s[mid]-s[l-1])+s[r]-s[mid]-1ll*a[mid]*(r-mid);
}
bool check(int x) {
    int i;
    for(i=1;i<=n-x+1;i++) {
        if(solve(i,i+x-1)<=B) return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d%lld",&n,&L,&B);
    int i;
    for(i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    int l=1,r=n+1;
    while(l<r) {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    printf("%d",l-1);
}