PASCAL 数列分段

二分答案,即二分查找每段的最大和
首先设一个值,我这里是S,这个是假设的分段和的最大值,然后依据这个S来进行贪心分组(容易证明贪心的正确性),分组结果和m比较,然后决定增大S还是减少S.

var i,j,k,l,n,m,t1,t2,s,g:longint;
a:array[1..100010]of longint;

function max(a,b:longint):longint;
begin
if(a>b)then exit(a);
exit(b);
end;

function divide:longint;
var i,k,t:longint;
begin
k:=0;
t:=0;
for i:=1 to n do begin
if(t+a[i] > s)then begin
t:=0;
inc(k);
end;
inc(t,a[i]);
end;
inc(k);
exit(k);
end;

begin
readln(n,m);
for i:=1 to n do begin
read(a[i]);
s:=max(s,a[i]);
inc(t2,a[i]);
end;

t1:=s;

s:=s*2;

repeat
k:=divide();
if(k>m)then begin
t1:=s+1;
s:=(t1+t2)div 2;
end
else begin
t2:=s-1;
s:=(t1+t2)div 2;
end;
until t1>=t2;
writeln(t2);
end.

师大附中的题吧 ？
var
a:array[0..100000] of longint;
n,k,min,max,ans:longint;
//=================================
procedure init;
var
i:longint;
begin
readln(n,k);
min:=0;
max:=0;
for i:=1 to n do
begin
read(a[i]);
if min max:=max+a[i];
end;
end;
//=================================
function cut(m:longint):boolean;
var
sum,num,i:longint;
begin
sum:=0;
num:=1;
for i:=1 to n do
if sum+a[i]>m then
begin
inc(num);
sum:=a[i];
end
else
sum:=sum+a[i];
if num>k then exit(false)
else exit(true);
end;
//================================
procedure search;
var
l,r,mid:longint;
begin
l:=min; r:=max;
while l<>r do
begin
mid:=(l+r) shr 1;
if cut(mid) then r:=mid
else l:=mid+1;
end;
ans:=l;
end;
//================================
procedure print;
begin
writeln(ans);
end;
//================================
begin
assign(input,'divide_b.in');
reset(input);
assign(output,'divide_b.out');
rewrite(output);
init;
search;
print;
close(input);
close(output);
end.
思路汤哥的PPT有呀 就是二分

哥，我服了