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

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

1. Đề bài TWO Spoj

Có N chi tiết máy cần được gia công lần lượt trên 2 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]. Hãy tìm trình tự gia công các chi tiết trên 2 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ể.

Input

  • Dòng 1: số nguyên dương N (1 ≤ N ≤ 10000).
  • Dòng 2: N số nguyên dương a[1], …, a[n]. (1 ≤ a[i] ≤ 10000)
  • Dòng 3: N số nguyên dương b[1], …, b[n]. (1 ≤ b[i] ≤ 10000)

Output

  • Dòng 1: Số nguyên dương T là thời điểm sớm nhất có thể hoàn thành.
  • Dòng 2: N số nguyên là lịch trình gia công các chi tiết máy.

Example

Input:

3

2 3 1

1 2 3

Output:

7

3 2 1

2. Gợi ý TWO Spoj

– Các bạn dùng thuật toán Jonhson ^^

3. Code Tham Khảo TWO Spoj

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.

One thought on “TWO Spoj – Lập lịch trên hai máy

  1. CHO MÌNH HỎI TÁI SAO thuật toán JONHSON BỊ SAI:

    Chia các chi tiết thành 2 nhóm: nhóm 1, gồm các chi tiết Ni thoả mãn ai bi tức là min(ai,bi)=bi. Các chi tiết Ni thoả mãn ai =bi xếp vào nhóm nào cũng được.
    Sắp xếp các chi tiết trong Nhóm1 theo chiều tăng của các ai và sắp xếp các chi tiết trong Nhóm2 theo chiều giảm của các bi
    Nối Nhóm2 vào đuôi Nhóm1, dãy thu được (đọc từ trái sang phải) sẽ là lịch gia công.

    ví dụ

    2

    3 2

    2 1

    thì thuật toán trên cho lịch trình là 1->2 với thời gian là 6.

    nhưng nếu theo 2->1 thì thời gian là 5

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *