9.9 买礼物的艰辛 2719
【9.9 买礼物的艰辛 2719】
- 题目
- 题解
- 代码
题目 小X同学给小C同学选了N件礼物，决定顺序购买并赠送，但作为一个没有工资没有零花钱的可怜小朋友，有M位好心的同学伸出了援助之手，然而为了减少最高的借款量，小X同学希望OI竞赛的你为他合理规划，使得他能轻松快乐地送出礼物。
100%: n<=100000
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
题解 最大值的最小值，二分啦
注意：顺序购买。如样例，不能买了100然后买101
时间复杂度O(n log n)
代码 这坨跑得快一点
var
n,m,i,j,k,l,r,t,mid,ans:longint;
a:array[1..100000]of longint;
begin
readln(n,m);
for i:=1 to n do
begin
readln(a[i]);
k:=k+a[i];
end;
r:=k;
l:=1;
while lmid then begin j:=m+1;
break;
end else
begin
if t+a[i]>mid then begin t:=0;
inc(j);
end;
t:=t+a[i];
end;
if j<=m then
r:=mid else
l:=mid+1;
end;
writeln(r);
end. 这坨慢一点
var
n,m,i,j,k,l,r,mid,ans:longint;
a:array[1..100000]of longint;
function night(k:longint):boolean;
var
i,j,l,r,t:longint;
begin
t:=0;
j:=0;
for i:=1 to n do
if a[i]>k then exit(false) else
begin
if t+a[i]>k then begin t:=0;
inc(j);
end;
t:=t+a[i];
end;
if j>m then exit(false);
exit(true);
end;
begin
readln(n,m);
for i:=1 to n do
begin
readln(a[i]);
k:=k+a[i];
end;
r:=k;
l:=1;
while l推荐阅读
- 有句话忍很久了，女生要求买房怎么就物质了（）
- 六一礼物
- 爸爸带我买文具。
- 《有味》（做一个人间的烟火神仙）
- 七夕情浓（高逼格的单身生活，还得拿钱买单）
- 离别的话
- 2018-11-27今天属于宇宙，这是我送给他的礼物|2018-11-27今天属于宇宙，这是我送给他的礼物|我的奇迹日记Day27
- 孩子，你幼儿园毕业前，最好的礼物是来自老师们爱你的“反馈”！
- 近日生活教训
- 每月要挣多少钱，才能买到快乐（）