首页 > 代码库 > [Ioi2011]ricehub
[Ioi2011]ricehub
2600: [Ioi2011]ricehub
Time Limit: 10 Sec Memory Limit: 128 MB[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
收集的稻米肯定在一段连续的区间内
所以,如果固定区间左端点,那么区间右端点的取值具有单调性
单调性解释:若r1<r2,那么[l,r1]的花费一定小于[l,r2]的花费
所以可以枚举左端点,二分右端点,判断标准时区间花费是否<=B
判断时用前缀和优化,O(1)出结果
#include<cstdio>#include<algorithm>#define N 100001using namespace std;int R;long long L,B;long long pos[N],sum[N];int ans,p;long long read(long long &x){ x=0; char c=getchar(); while(c<‘0‘||c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); }}long long check(int l,int r){ p=l+r>>1; return pos[p]*(p-l)-sum[p-1]+sum[l-1]+sum[r]-sum[p]-pos[p]*(r-p);}int main(){ scanf("%d",&R); read(L); read(B); for(int i=1;i<=R;i++) read(pos[i]),sum[i]=sum[i-1]+pos[i]; int l,r,mid,tmp,p; for(int i=1;i<=R;i++) { l=i; r=R; while(l<=r) { mid=l+r>>1; if(check(i,mid)<=B) { l=mid+1; tmp=mid; } else r=mid-1; } ans=max(ans,tmp-i+1); } printf("%d",ans);}
[Ioi2011]ricehub
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。