首页 > 其他 > 详细

[NOI2010]航空管制

时间:2019-01-02 23:01:47      阅读:182      评论:0      收藏:0      [点我收藏+]

二元组的限制

考虑拓扑排序

正向拓扑不能保证最优,因卡的是结束时间

所以方向建图topo

从n为0时间,

相当于在n-k[i]的时间出现一架飞机

小根堆维护,每次选择当前最早出现的一架飞机起飞。

由于保证有解,这个显然是正确的,对于当前只有一架飞机,不飞白不飞(当然也不能不飞);多架飞机,先飞后飞反正都是要飞,所以随便飞一个

 

第二问受第一问启发,如果找到了当前飞机i,先不放进堆里面,如果当前没有了飞机可以飞,就让i飞。

实际上,我们是故意让i飞机来了不飞,等着同一时间别的飞机飞完(上面第一问的证明可以保证这样还是有解),自己再飞(这个时候必须要飞了)。

 

倒序topo考虑是一个关键点

因为卡的是截止时间,从前往后,并不知道先放谁更好,

而如果倒着,相当于某个时刻有了一个可以有的决策,往往比一个东西可能会过期处理起来方便

例如:[NOI2017]蔬菜——时光倒流+贪心

再如:

[NOI2010]航空管制

原文:https://www.cnblogs.com/Miracevin/p/10211587.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!