Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKTARDY - Lập lịch giảm thiểu trễ hạn

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:

  • pi là thời gian cần thiết để hoàn thành công việc i.
  • di 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ử ci là thời điểm hoàn thành công việc i. Khi đó, nếu ci > di ta nói công việc i bị hoàn thành trễ hạn, còn nếu ci ≤ di 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 p1, p2, ..., pn (0 < pi ≤ 10000).
  • Dòng thứ ba chứa n số nguyên dương d1, d2, ..., dn (0 < di ≤ 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

Được gửi lên bởi:Duc
Ngày:2008-01-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED

hide comments
2017-02-16 10:20:44
More là cái gì vậy
2016-05-13 16:21:13
nếu có nhiều trình tự thỏa mãn thì in ra cái nào cũng được phải ko


Last edit: 2016-05-13 16:22:12
2016-04-03 03:50:55
AC! Xài More là OK Rồi! K cần vắt não QHD đâu :V
2015-09-30 04:12:08 Nguyễn Vĩnh Thịnh
O(n.logn) có vấn đề j mà 70 nhỉ
2015-09-12 04:11:23


Last edit: 2015-09-12 04:11:43
2015-09-08 14:22:53
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-08-14 16:35:58
tham lam trong sach @@
2015-05-24 05:39:59 df
Cham sai
2015-01-19 08:29:23 Bee
Sai rồi bạn !
Input :
8
3 5 2 7 9 2 6 2
5 1 7 3 9 2 5 7
Output :
5
1 3 8 2 4 5 6 7
THAM LAM
2014-10-14 15:30:32 ๖ۣۜRεus
ai cho xem hộ với ạ
input là 8
3 5 2 7 9 2 6 2
5 1 7 3 9 2 5 7
output ra bn ạ ?? mình ra 7
6 2 1 8 3 4 7 5
đúng ko các bạn
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.