洛阳好的化妆学校:oi ---pascal

先按bi/ai从大到小排列部件，再进行回溯搜索，搜索过程中尽量去除无用分支。

program gongxu;

{$APPTYPE CONSOLE}

uses
SysUtils,Math;

const
max_n = 100;

type
TPart = record
a,b:integer;
w:real;
used:boolean;
end;
TOrder = array[1..max_n] of integer;

var
parts:array[1..max_n] of TPart;
order:TOrder;
min_order:TOrder;
i,n,total_a,total_b,min_value,count:integer;
infile,outfile:text;

procedure sort(l,r:integer);
var
i,j,m:integer;
w0:real;
t:TPart;
begin
if (l > r)
then
exit;
i := l;
j := r;
m := (l+r) div 2;
w0 := parts[m].w;
t := parts[m];
parts[m] := parts[l];
parts[l] := t;
inc(i);
while (i <= j)
do
begin
while (i <= j) and (parts[i].w >= w0)
do
inc(i);
while (i <= j) and (parts[j].w <= w0)
do
dec(j);
if (i <= j)
then
begin
t := parts[i];
parts[i] := parts[j];
parts[j] := t;
end;
end;
t := parts[j];
parts[j] := parts[l];
parts[l] := t;
sort(l,j-1);
sort(j+1,r);
end;

procedure try_it(index,ca,cb,ta,tb:integer);
var
i,value,ca_new,cb_new,j:integer;
bad:boolean;
begin
inc(count);
value := max(ca+ta,cb+tb);
if (value >= min_value)
then
exit;

if (index = n + 1)
then
begin
min_order := order;
min_value := value;
exit;
end;

for i := 1 to n
do
if (not parts[i].used)
then
begin
bad := false;
for j := 1 to n
do
if ((j <> i) and (not parts[j].used) and (parts[i].a >= parts[j].a) and (parts[i].b <= parts[j].b))
then
begin bad := true; break; end;
if (bad)
then
continue;
order[index] := i;
parts[i].used := true;
ca_new := ca + parts[i].a;
cb_new := max(ca_new,cb) + parts[i].b;
try_it(index+1,ca_new,cb_new,ta-parts[i].a,tb-parts[i].b);
parts[i].used := false;
end;
end;

begin
assign(infile,'input.txt');
assign(outfile,'output.txt');
reset(infile);
rewrite(outfile);
readln(infile, n);
total_a := 0;
total_b := 0;
for i := 1 to n
do
begin
readln(infile, parts[i].a, parts[i].b);
if (parts[i].a = 0)
then
parts[i].w := 1e+10
else
parts[i].w := parts[i].b/parts[i].a;
parts[i].used := false;
inc(total_a, parts[i].a);
inc(total_b, parts[i].b);
end;

sort(1,n);

min_value := total_a + total_b + 1;
count := 0;
try_it(1,0,0,total_a,total_b);

for i := 1 to n
do
writeln(outfile,parts[min_order[i]].a,' ',parts[min_order[i]].b);
writeln(outfile,'total=',min_value);
writeln(outfile,'count=',count);

close(infile);
close(outfile);
end.