sửa ô tô

[quanganhaq]

Mong các bạn giải giúp mình bài này với!
có n ô tô cần chữa, thông tin về oto thứ i bao gồm: di,ti (với di là hạn định phải sửa xong oto; ti là thời gian cần thiết để sửa oto). Nhà máy làm việc ko ngừng cho đến khi mọi oto dc sửa xong; tại mỗi thời điểm, nhà máy chỉ xử lý được một oto; sửa xong oto này mới sửa được oto khac.
Yêu cầu: hãy lập kế hoạch để số oto sửa đúng hạn là nhiều nhất.
vd: file 'oto.inp'
(dòng đầu là số nguyên dương n (n<=1000)
n dòng tiếp theo, mỗi dòng là thông tin của một oto: di và ti)

oto.inp
7
7 3
5 2
8 4
12 4
17 6
9 2
20 5

oto.out
5
16
(dòng đầu của file oto.out la số lượng oto sửa đúng hạn nhiều nhất
dòng thứ hai là thời gian tương ứng).
:-?[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[sonanh3082]

Mong các bạn giải giúp mình bài này với!
có n ô tô cần chữa, thông tin về oto thứ i bao gồm: di,ti (với di là hạn định phải sửa xong oto; ti là thời gian cần thiết để sửa oto). Nhà máy làm việc ko ngừng cho đến khi mọi oto dc sửa xong; tại mỗi thời điểm, nhà máy chỉ xử lý được một oto; sửa xong oto này mới sửa được oto khac.
Yêu cầu: hãy lập kế hoạch để số oto sửa đúng hạn là nhiều nhất.
vd: file 'oto.inp'
(dòng đầu là số nguyên dương n (n<=1000)
n dòng tiếp theo, mỗi dòng là thông tin của một oto: di và ti)

oto.inp
7
7 3
5 2
8 4
12 4
17 6
9 2
20 5

oto.out
5
16
(dòng đầu của file oto.out la số lượng oto sửa đúng hạn nhiều nhất
dòng thứ hai là thời gian tương ứng).
:-?[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Dạng bài này là 1 trong những lớp bài toán tớ ngán nhất :|
Thuật toán:
- Sắp xếp theo thứ tự tăng dần thời điểm hạn định phải sửa ô tô xong.
- Duyệt từ đầu cho đến khi gặp công việc bị trễ hạn đầu tiên (có thời gian làm từ đầu đến công việc này lớn hơn hạn định)
Gọi k là công việc trễ hạn đầu tiên tìm được. Tìm max ti với i thuộc [1..k], nếu công việc đó được chuyển 1 lần thì dừng, ngược lại đem nó xuống cuối, quay lại tiếp tục làm bước duyệt.
Theo như output, kết quả sẽ là:
Sau khi kết thúc thuật toán: duyệt đếm để in ra số lượng. Trong khi duyệt lưu thời gian sửa ô tô tổng. In ra [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[mallboro]

Bài này binhnguyen nói đúng rồi đó, thuật toán tham lam để giải quyết. Để hiểu được vì sao nó lại đúng thì hơi phức tạp, tuy nhiên cũng chứng minh được. Còn chứng minh thế nào thì [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] mình cũng quên béng mất rồi.