Nguồn đề bài: http://vn.spoj.com/problems/NK2MFS/
Nội dung bài viết
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à ai, thời gian gia công trên máy B là bi.
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 a1, a2… an (1 ≤ ai ≤ 10000)
- Dòng thứ ba chứa N số nguyên dương b1, b2,… bn (1 ≤ bi ≤ 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:
3
2 3 1
1 2 3
Output:
7
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
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. |
Bài viết liên quan
- TWO Spoj – Lập lịch trên hai máy
- P146PROG spoj PTIT – Cuộc thi ăn socola
- P145PROD spoj PTIT – Diện tích hình tròn
- P142PROC spoj PTIT – Tập chơi cờ vua
- P141SUMB spoj PTIT – ROUND 1B – Hoán vị
- P134SUMF spoj PTIT – SUM4 F – Sàng nguyên tố
- P132SUMD spoj PTIT – SUM2 D – Thực hiện phép tính
- P131SUMH spoj PTIT – SUM1 H – KANGUROO
- GOODFRIE spoj PTIT – Good friends
- BCPOW spoj PTIT – Lũy thừa