2600: [Ioi2011]ricehub
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 475 Solved: 247
[Submit][Status][Discuss]
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
这题据说是IOI里最水的一题。。。其实确实很简单
显然的对于一个已知的区间【L,R】收益最多的是中位数。我们枚举L，R是递增的，所以可以用单调队列维护，判断是否要R++可以用前缀和什么的随便搞搞。。
细节：因为坐标较大。。所以要用long long!!!!!!!
然后我就被坑WA了4发。。。
#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
long long x[N],sum[N];
long long n,l,m,R,L,ans;
long long OK(int R){
int mid = (L+R)>>1;
long long tmp1 = x[mid]*(mid-L)-(sum[mid-1]-sum[L-1]);
long long tmp2 = (sum[R]-sum[mid])-x[mid]*(R-mid);
return tmp1+tmp2;
}
int main(){
scanf("%lld%lld%lld",&n,&l,&m);
for (int i=1;i<=n;i++) scanf("%lld",&x[i]),sum[i] = sum[i-1]+x[i];
R = 1;
for (L=1;L<=n;L++){
while (R<n && OK(R+1)<=m) R++;
if (R-L+1>ans) ans = R-L+1;
}
printf("%lld",ans);
}
评论 (0)
