BZOJ 2336 [HNOI2011] 任务调度

发布于 2017-04-21  308 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2336

题意:n 个任务,AB 两个机器,每个任务都需要在 A 做一段,B 做一段。有的任务必须先在 A 上做,有的必须先在 B 上做,有的没有限制,问最短时间。


搞了一上午... 始终 WA 一个点,以为掉进了玄学调参的深坑,结果发现是傻逼的忘记初始化 cnt....

我们枚举 (或随机) 没有限制的任务,将它们归入有限制的任务类型,这样就只需要考虑 k=1 和 2 的情况

然后贪心排序,随机交换两个任务,看看是否更优,可能是 bzoj 太水,只交换 20 次也能过 orz

代码如下:

 


一个非常弱的准退役OIER