注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【找不到出处】最大值最小化  

2013-07-15 21:21:32|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
把一个包含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.


  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018