NOI2010 航空管制

　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　


　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　



先附個題目連結，

http://hi.baidu.com/%D2%DD%C3%F7%BE%A8%C8%CB/blog/item/4bb3383d07f175cf7d1e71d5.html





第一部分很簡單，就把所有限制建構成一個DAG，



把頂點依照"最遲起飛時間"排序，由小到大儘量滿足即可。



由於保證有解，所以這部分相信不是大問題。複雜度O(N+M)









第二部分先講一下我首先想到的想法：



如果該架飛機的起飛時間在[1, K]之間，然後我們二分搜K顯然可以得到答案。



二分搜之後我們可以變成把該節點的最遲起飛時間變成K，然後做一次第一題檢查是否有解



對每個的複雜度是O((N+M)lgN)，總複雜度約O(NMlgN)



而且其實二分搜的範圍很小，應該運行速度不會太慢。





如果有把第一題弄成一個function實作難度會降低很多。





另外附一個剛才在網路上找到的不錯思路：



http://yzm-blog.appspot.com/2010/08/8/NOI-2010.html



用Heap實作，複雜度差不多。