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.

Download