二分答案——划分数列

COGS p917 划分数列

【分析】

即k序列和

可采用二分答案的思想，设出一个答案ans，循环将和不超过ans的几个数分为一部分。直到最后若可以分为k部分则减小上界，反之增加下界。直到确定答案。

 

var
  n,k,i,p,l,r,m,s:longint;
  a:array[1..100000] of longint;
begin
assign(input,'seqa.in');
reset(input);
assign(output,'seqa.out');
rewrite(output);
  readln(n,k);
  for i:=1 to n do
  begin
    read(a[i]); inc(r,a[i]);
  end;
  while r-l>1 do begin
    m:=(l+r) shr 1;
    s:=0; p:=0;
    for i:=1 to n do
      if s+a[i]<=m then s:=s+a[i]
        else begin inc(p); s:=a[i]; end;
    if p+1>k then l:=m else r:=m;
  end;
  writeln(r);
close(input);
close(output);
end.