Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

简略解题报告

Posted by xuhaoran510 at 2011-07-06 10:12:49 on Problem 2751
为了使浪费(有机器闲置)的时间尽量少,我们应让s2等待的时间尽量短。
所以我们应尽量让s2的任务越堆越多。因此,我们应优先加工s1<s2的任务(这样才能让S2的任务堆积起来)
如果加工某个任务s时,s1的加工时间超过了目前s2堆积的任务量,那么s2就会加工完所有的任务然后等待s1的完成,这是我们不愿看到的。因此我们应先加工s1小的任务,这样上面的情况就更难出现,而且积累更多的任务也有利于尽量减少加工更大的S1时的等待时间,符合贪心原则。
等到所有s1<s2的任务都加工完了,可以证明我们应该先加工S2最大的任务,这样也是符合贪心原则的。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator