首页 > 代码库 > lydsy 2600(二分+中位数前缀和)米仓
lydsy 2600(二分+中位数前缀和)米仓
2600: [Ioi2011]ricehub
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 691 Solved: 359
[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
HINT
Source
var i,j:longint; r,l,ans,num,x,y,mid,b,n:int64; a,f:array[0..200000] of int64; function pd(mid:int64):boolean; var i,j:longint; m,sum:int64; begin for i:=1 to n-mid+1 do begin j:=i+mid-1; m:=(i+j) div 2; sum:=f[j]+f[i-1]-f[m]-f[m-1]+a[m]*(m-i)-a[m]*(j-m); //最重要的一句(记) if sum<=b then exit(true); end; exit(false); end; begin readln(n,y,b); for i:=1 to n do begin read(a[i]); f[i]:=f[i-1]+a[i]; end; l:=1; r:=n; while r>=l do begin mid:=(r+l) div 2; if pd(mid) then begin ans:=mid; l:=mid+1; end else r:=mid-1; end; writeln(ans); end.
lydsy 2600(二分+中位数前缀和)米仓
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。