(6 ĐIỂM) SẮP XẾP VIỆCCÓ N CÔNG VIỆC CẦN THỰC HIỆN TRÊN MỘT MÁY TÍNH,...

Bài 4 : (6 điểm) Sắp xếp việc

Có n công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi đúng 1 giờ máy. Với mỗi

việc ta biết thời hạn phải nộp kết quả thực hiện sau khi hoàn thành việc đó và tiền thưởng thu được

nếu nộp kết quả trước hoặc đúng thời điểm quy định. Chỉ có một máy tính trong tay, hãy lập lịch

thực hiện đủ n công việc trên máy tính sao cho tổng số tiền thưởng thu được lớn nhất với thời gian

hoạt động của máy là nhỏ nhất. Giả thiết rằng máy được khởi động vào đầu ca, thời điểm t = 0 và

chỉ tắt máy sau khi đã hoàn thành đủ n công việc.

Dữ liệu: vào từ file văn bản WORK.INP

• Dòng 1: chứa số nguyên dương n (3  n  100)

• N dòng tiếp theo: mỗi việc được mô tả bằng 2 số tự nhiên, số thứ nhất là thời hạn giao

nộp, số thứ 2 là tiền thưởng. Các số cách nhau bởi dấu cách.

Ví dụ:

WORK.INP Ý nghĩa: cho biết 5 công việc với các nội dung sau

- Việc thứ nhất không nộp muộn hơn thời điểm 2 (giờ) với tiền

5

2 15

thưởng là 15 (ngàn đồng);

1 17

- Việc thứ hai không nộp muộn hơn thời điểm 1 (giờ) với tiền

3 60

thưởng là 17 (ngàn đồng);

1 30

- Việc thứ ba không nộp muộn hơn thời điểm 3 (giờ) với tiền

5 120

thưởng là 60 (ngàn đồng);

- Việc thứ tư không nộp muộn hơn thời điểm 1 (giờ) với tiền

thưởng là 30 (ngàn đồng);

- Việc thứ năm không nộp muộn hơn thời điểm 5 (giờ) với tiền

thưởng là 120 (ngàn đồng);

Kết quả: Ghi ra file văn bản WORK.OUT

• N dòng đầu tiên, dòng thứ t ghi một số tự nhiên i cho biết việc thứ i được làm trong giờ t

• Dòng cuối cùng ghi tổng số tiền thu được.

WORK.OUT Ý nghĩa:

- Giờ thứ 1 thực hiện việc 4 và nộp đúng hạn nên được

4

1

thưởng 30;

3

- Giờ thứ 2 thực hiện việc 1 và nộp đúng hạn nên được

5

thưởng 15;

2

- Giờ thứ 3 thực hiện việc 3 và nộp đúng hạn nên được

225

thưởng 60;

- Giờ thứ 4 thực hiện việc 5 và nộp trước hạn nên được

thưởng 120;

- Giờ thứ 5 thực hiện việc 2

- Tổng tiền thưởng thu được do hoàn thành đúng hạn bốn

việc 4, 1,3 và 5: 30 + 15 + 60 + 120 = 225