编程介的小学生
2017-09-10 16:16Parts Process
To build a machine, a lot of parts need to be produced. A question is how to arrange the processing order to minimize the total delay time of the parts.
Input
The input consists of no more than 20 test cases.
The first line of each test case contains an integer n (<= 15). Then n lines follow.
The i-th (start from 1) line contains two positive integers pi and di, where pi is the i-th part's process time (that is, pi minute(s) must be taken to produce the i-th part), and di the deadline of the i-th part.
These lines are in ascending order of di. The total process time is no more than 100.
Output
Define:
Fi - the finishing time of the i-th part;
Di - the delay time of the i-th part, that is, Di = max{(Fi - di) , 0};
T - the total delay time, that is, T = sum(Di).
For each test case, two lines should be outputted.
The first line contains the minimal T.
The second line contains n integers, indicating the processing order of the parts.
If there are more than one orders, you should output the lexicographically smaller one.
Sample Input
3
3 3
2 3
1 20
Sample Output
2
1 2 3
- 点赞
- 回答
- 收藏
- 复制链接分享
1条回答
为你推荐
- 获取调用函数的名称和包
- it技术
- 互联网问答
- IT行业问题
- 计算机技术
- 编程语言问答
- 1个回答
- 将原始Goreq.body响应附加到文件
- it技术
- 互联网问答
- IT行业问题
- 计算机技术
- 编程语言问答
- 2个回答
- 在Go中有效处理许多大文件的HTTP上传
- http
- 2个回答
- 如何在PHP中将HTML字符串拆分为块? [重复]
- substring
- php
- 3个回答
- Paypal IPN监听器总是返回INVALID,但事务在paypal中成功
- paypal
- php
- 2个回答