02/10/2018, 14:44
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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | 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. |
