NKTARDY - Lập lịch giảm thiểu trễ hạn
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Có n công việc đánh số từ 1 đến n và một máy để thực hiện chúng. Biết:
- p i là thời gian cần thiết để hoàn thành công việc i.
- d i là thời hạn hoàn thành công việc i.
Máy bắt đầu hoạt động từ thời điểm 0. Mỗi công việc cần được thực hiện liên tục từ lúc bắt đầu cho tới khi kết thúc, không cho phép ngắt quãng. Giả sử c i là thời điểm hoàn thành công việc i. Khi đó, nếu c i > d i ta nói công việc i bị hoàn thành trễ hạn, còn nếu c i ≤ d i thì ta nói công việc i được hoàn thành đúng hạn.
Yêu cầu: Tìm trình tự thực hiện các công việc sao cho số công việc hoàn thành trễ hạn là ít nhất.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương n (0 < n ≤ 100000).
- Dòng thứ hai chứa n số nguyên dương p 1 , p 2 , ..., p n (0 < p i ≤ 10000).
- Dòng thứ ba chứa n số nguyên dương d 1 , d 2 , ..., d n (0 < d i ≤ 10000).
Kết quả
- Dòng đầu tiên ghi số lượng công việc bị hoàn thành trễ hạn theo trình tự tìm được.
- Dòng tiếp theo ghi n số nguyên dương là chỉ số của các công việc theo trình tự thực hiện tìm được.
Hạn chế
- Có 50% số test có n ≤ 100.
Ví dụ
Dữ liệu 6 2 4 1 2 3 1 3 5 6 6 7 8 Kết quả 2 1 3 4 6 2 5
- Người up: paulmcvn