NK2MFS - Lập lịch trên hai máy
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
var
a,b:array[1..10111] of longint;
n,n1,n2,i:longint;
a1,b1,ind1,a2,b2,ind2:array[1..10111] of longint;
ta,tb:longint;
procedure swap(var a,b:longint);
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;
procedure sort1(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=a1[l+random(r-l+1)];
repeat
while a1[i]<mid do inc(i);
while a1[j]>mid do dec(j);
if i<=j then
begin
swap(a1[i],a1[j]);
swap(b1[i],b1[j]);
swap(ind1[i],ind1[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort1(i,r);
if l<j then sort1(l,j);
end;
procedure sort2(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=b2[l+random(r-l+1)];
repeat
while b2[i]>mid do inc(i);
while b2[j]<mid do dec(j);
if i<=j then
begin
swap(a2[i],a2[j]);
swap(b2[i],b2[j]);
swap(ind2[i],ind2[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort2(i,r);
if l<j then sort2(l,j);
end;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do read(b[i]);
for i:=1 to n do
if a[i]<b[i] then
begin
inc(n1);
a1[n1]:=a[i];
b1[n1]:=b[i];
ind1[n1]:=i;
end
else
begin
inc(n2);
a2[n2]:=a[i];
b2[n2]:=b[i];
ind2[n2]:=i;
end;
sort1(1,n1);
sort2(1,n2);
for i:=1 to n1 do
begin
inc(ta,a1[i]);
tb:=max(ta,tb)+b1[i];
end;
for i:=1 to n2 do
begin
inc(ta,a2[i]);
tb:=max(ta,tb)+b2[i];
end;
writeln(tb);
for i:=1 to n1 do
write(ind1[i],' ');
for i:=1 to n2 do
write(ind2[i],' ');
end.