【找不到出处】最大值最小化
2013-07-15 21:21:32| 分类：
AC题目
| 标签：
|举报
|字号大中小 订阅
把一个包含n个正整数的序列划分成m个连续的子序列(每个正整数恰好属于一个序列)。设第i个序列的各数之和为S(i)，你的任务是让所有的S(i)的最大值尽量小。例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5|4，其中S(1)=6，S(2)=7，S(3)=4，最大值为7；如果划分成1 2|3 2|5 4，则最大值为9；不如刚才的好。n<=10^6，所有数字之和不超过10^9。
========================================================================================================
这个问题一开始是想直接贪心的，即求出总和的平均数，然后再每次挑数，第一次超过的时候就划分界线。但是这样子并不能保证选择一定是最优的。所以想了一下就想起来了二分答案加贪心...因为题目中特意提到了数字之和不超过 10^9.......
首先在允许的范围内二分查找，每次找到一个值就检测是否存在这样一个方案，如果存在则向左边找，如果不存在则向右边找，然后最后就可以得到正解了，这个为 logN级别的复杂度，最大为30次左右的查找，然后对于每次检验，就像咱一开始想的使用贪心即可，每一次马上要超过的时候则划开区界，可以保证这样能够得到的解是最优解，假如这个最优解都满足不了条件，显然不符合，而如果符合了则向左继续找，每找到一个可行解就比较记录好。就这样就可以在 O(NlogS）（S为数据总和），最多的复杂度为3*10^7左右，可以过全部数据。
program min_max;
var n,m:longint;
s:longint;
a:array[1..1000000]of longint;
function test(p:longint):boolean;
var i,j,k:longint;
begin
j:=0;k:=1;
for i:=1 to n do
begin
if j+a[i]>p then begin inc(k);j:=0;end;
j:=j+a[i];
if j>p then begin inc(k);j:=0;end;
if k>m then exit(false);
end;
exit(true);
end;
procedure main;
var l,r,mid,ans:longint;
f:boolean;
begin
l:=0;r:=s+1;ans:=0;
while r-l>1 do
begin
f:=false;
mid:=(l+r)shr 1;
if test(mid) then
begin ans:=mid;
f:=true;end;
if f then r:=mid
else l:=mid;
end;
write(ans);
end;
procedure init;
var i:longint;
begin
assign(input,'min_max.in');reset(input);
assign(output,'min_max.out');rewrite(output);
read(n);read(m);
s:=0;
for i:=1 to n do
begin read(a[i]);s:=s+a[i];end;
main;
close(input);close(output);
end;
begin
init;
end.
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论