最近有个朋友问了一个算法分析的题目,感觉有点意思就在这里简单说一下自己的思路吧!
题目:
突击战:
你有 n 个部下, n 个任务,你计划让部下 i 去做任务 i (1<=i< =n ) ,但部下还不知道任务 的内容,需要你为每个部下解释任务内容(即交代任务)。第 i 个部下需要你花 B(i) 分钟交 代任务,然后他会立刻、独立地、无间断地执行 J( i) 分钟后完成任务。你每次只能给一个 部下交代任务,但部下们可以同时执行各自的任务。 问题:交代任务的顺序不同,完成所有任务所用的时间也不同。你需要考虑的是交代任务的 顺序,在最短的时间内完成所有任务。 输入:每个部下交代任务需要的时间 B(i) 和执行自己任务需要的时间 J(i) ,其中 1<=i< =n
输入格式:第一行输入部下数 n (它也是任务数) 后面的 n 行,每行两个数字,分别对应 B(i) 和 J (i)
输出: 1~ n 的一个排列(对应 n 个部下的交代任务次序),以及这种安排下所有任务的完成 时间
具体分析:
参考:http://blog.csdn.net/jodenhe/article/details/73087662