Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
简略解题报告为了使浪费(有机器闲置)的时间尽量少,我们应让s2等待的时间尽量短。 所以我们应尽量让s2的任务越堆越多。因此,我们应优先加工s1<s2的任务(这样才能让S2的任务堆积起来) 如果加工某个任务s时,s1的加工时间超过了目前s2堆积的任务量,那么s2就会加工完所有的任务然后等待s1的完成,这是我们不愿看到的。因此我们应先加工s1小的任务,这样上面的情况就更难出现,而且积累更多的任务也有利于尽量减少加工更大的S1时的等待时间,符合贪心原则。 等到所有s1<s2的任务都加工完了,可以证明我们应该先加工S2最大的任务,这样也是符合贪心原则的。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator