NK2MFS Spoj - Lập lịch trên hai máy

Nguồn đề bài: http://vn.spoj.com/problems/NK2MFS/

Nội dung bài viết

1. Đề bài NK2MFS Spoj
2. Gợi ý NK2MFS Spoj – Lập lịch trên hai máy
3. Code Tham Khảo NK2MFS Spoj – Lập lịch trên hai máy

1. Đề bài NK2MFS Spoj

Có N chi tiết máy cần được gia công lần lượt trên hai máy A và B. Thời gian gia công chi tiết i trên máy A là a_i, thời gian gia công trên máy B là b_i.

Yêu cầu: hãy tìm trình tự gia công các chi tiết trên hai máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất có thể.

Dữ liệu

Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10000).
Dòng thứ hai chứa N số nguyên dương a₁, a₂… a_n (1 ≤ a_i ≤ 10000)
Dòng thứ ba chứa N số nguyên dương b₁, b₂,… b_n (1 ≤ b_i ≤ 10000).

Kết quả

Dòng đầu tiên chứa số nguyên dương T là thời điểm sớm nhất có thể hoàn thành.
Dòng thứa hai chứa N số nguyên cho biết lịch trình gia công các chi tiết máy.

Ví dụ

Input:

2 3 1

1 2 3

Output:

3 2 1

2. Gợi ý NK2MFS Spoj – Lập lịch trên hai máy

– Thật ra đây là bài TWO phiên bản OI thôi. Các bạn xài Jonhson thì AC 😀

3. Code Tham Khảo NK2MFS Spoj – Lập lịch trên hai máy

var a,b,n1a,n1b,n2a,n2b:array[0..10000]of integer;
    n,i,n1,n2:integer;
    sa,sb:longint;
procedure sortt(l,r:integer);
 var d,c,tam:integer;
     mid:real;
  begin
    d:=l;
    c:=r;
    mid:=n1b[(l+r) div 2];
    repeat
      while n1b[d]<mid do inc(d);
      while n1b[c]>mid do dec(c);
      if d<=c then
        begin
          tam:=n1b[d];n1b[d]:=n1b[c];n1b[c]:=tam;
          tam:=n1a[d];n1a[d]:=n1a[c];n1a[c]:=tam;
          inc(d); dec(c);
        end;
    until d>c;
    if l<c then sortt(l,c);
    if d<r then sortt(d,r);
  end;
procedure sortg(l,r:integer);
 var d,c,tam:integer;
     mid:real;
  begin
    d:=l;
    c:=r;
    mid:=n2b[(l+r) div 2];
    repeat
      while n2b[d]>mid do inc(d);
      while n2b[c]<mid do dec(c);
      if d<=c then
        begin
          tam:=n2b[d];n2b[d]:=n2b[c];n2b[c]:=tam;
          tam:=n2a[d];n2a[d]:=n2a[c];n2a[c]:=tam;
          inc(d); dec(c);
        end;
    until d>c;
    if l<c then sortg(l,c);
    if d<r then sortg(d,r);
  end;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do
    begin
      read(b[i]);
      if a[i]<b[i] then
        begin
          n1:=n1+1;
          n1a[n1]:=i;
          n1b[n1]:=a[i];
        end else
          begin
            n2:=n2+1;
            n2a[n2]:=i;
            n2b[n2]:=b[i];
          end;
    end;
  sortt(1,n1);
  sortg(1,n2);
  sa:=a[n1a[1]]; sb:=a[n1a[1]]+b[n1a[1]];
  for i:=2 to n1 do
    begin
      sa:=sa+a[n1a[i]];
      if sa>=sb then sb:=sa+b[n1a[i]] else sb:=sb+b[n1a[i]];
    end;
  for i:=1 to n2 do
    begin
      sa:=sa+a[n2a[i]];
      if sa>=sb then sb:=sa+b[n2a[i]] else sb:=sb+b[n2a[i]];
    end;
  writeln(sb);
  for i:=1 to n1 do write(n1a[i],' ');
  for i:=1 to n2 do write(n2a[i],' ');
end.

var a,b,n1a,n1b,n2a,n2b:array[0..10000]of integer;

n,i,n1,n2:integer;

sa,sb:longint;

procedure sortt(l,r:integer);

var d,c,tam:integer;

mid:real;

begin

d:=l;

c:=r;

mid:=n1b[(l+r) div 2];

repeat

while n1b[d]<mid do inc(d);

while n1b[c]>mid do dec(c);

if d<=c then

begin

tam:=n1b[d];n1b[d]:=n1b[c];n1b[c]:=tam;

tam:=n1a[d];n1a[d]:=n1a[c];n1a[c]:=tam;

inc(d); dec(c);

end;

until d>c;

if l<c then sortt(l,c);

if d<r then sortt(d,r);

end;

procedure sortg(l,r:integer);

var d,c,tam:integer;

mid:real;

begin

d:=l;

c:=r;

mid:=n2b[(l+r) div 2];

repeat

while n2b[d]>mid do inc(d);

while n2b[c]<mid do dec(c);

if d<=c then

begin

tam:=n2b[d];n2b[d]:=n2b[c];n2b[c]:=tam;

tam:=n2a[d];n2a[d]:=n2a[c];n2a[c]:=tam;

inc(d); dec(c);

end;

until d>c;

if l<c then sortg(l,c);

if d<r then sortg(d,r);

end;

begin

readln(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do

begin

read(b[i]);

if a[i]<b[i] then

begin

n1:=n1+1;

n1a[n1]:=i;

n1b[n1]:=a[i];

end else

begin

n2:=n2+1;

n2a[n2]:=i;

n2b[n2]:=b[i];

end;

sortt(1,n1);

sortg(1,n2);

sa:=a[n1a[1]]; sb:=a[n1a[1]]+b[n1a[1]];

for i:=2 to n1 do

begin

sa:=sa+a[n1a[i]];

if sa>=sb then sb:=sa+b[n1a[i]] else sb:=sb+b[n1a[i]];

end;

for i:=1 to n2 do

begin

sa:=sa+a[n2a[i]];

if sa>=sb then sb:=sa+b[n2a[i]] else sb:=sb+b[n2a[i]];

end;

writeln(sb);

for i:=1 to n1 do write(n1a[i],' ');

for i:=1 to n2 do write(n2a[i],' ');

end.

NK2MFS Spoj – Lập lịch trên hai máy

1. Đề bài NK2MFS Spoj

Dữ liệu

Kết quả

Ví dụ

2. Gợi ý NK2MFS Spoj – Lập lịch trên hai máy

3. Code Tham Khảo NK2MFS Spoj – Lập lịch trên hai máy

Bài viết liên quan

Trả lời Hủy