level 7
偶做的
比搜索快 比DP慢一点点
var a:array [1..20000] of longint;
i,j,n,m,min,temp:longint;
procedure try(x,y:longint);
var i,j:longint;
begin
for i:=y+1 to m do
if x>=a[i] then begin x:=x-a[i]; try(x,i); x:=x+a[i]; end;
if x<min then min:=x;
end;
procedure qsoft(l,r:longint);
var t,k,i,j:longint;
begin
i:=l;j:=r;
k:=a[(l+r)div 2];
repeat
while k<a[i] do inc(i);
while k>a[j] do dec(j);
if i<=j then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if j>l then qsoft(l,j);
if i<r then qsoft(i,r);
end;
begin
assign(input,'pack.in');
reset(input);
assign(output,'pack.out');
rewrite(output);
read(n,m); min:=maxlongint;
for i:=1 to m do
read(a[i]);
qsoft(1,m);
try(n,0);
writeln(min);
close(input); close(output);
end.
求观摩
2011年07月11日 02点07分
