CSP2021S2T1 廊橋配置設定 題解

目錄

題目大意

題目解析

題目傳送門

一個機場裡面有 \(n\) 個廊橋，有 \(m1\) 架國内航班和 \(m2\) 架國際航班。每一架航班都有到達和離開的時間，保證所有飛機到達和離開的時間互不相同。

現在你需要把廊橋分成兩部分，一部分隻允許國際航班停靠，剩下的隻允許國内航班停靠。機場的廊橋實行先到先得的規則，如果沒有廊橋停靠就會停靠在遠機位。

現在請問怎麼配置設定廊橋能使能停在廊橋的飛機數量最多，現在要求這個最大值是多少。

\(n\le 10^5,1\le m1+m2 \le 10^5.\)

首先先講一下我的錯解。。。

顯然我們發現，随着分給國内機場的廊橋的改變，能停靠在廊橋的航班也會改變，并且是一個單峰函數，直接三分即可。

但是顯然我們發現 CCF 給的大樣例就不滿足是單峰函數，座椅這是錯的。

我們可以假設有國内航班和國外航班無數個位置，編号為 \(1,2,\dots n\)，如果飛機盡量往編号小的地方停靠，那麼無論選擇前面的編号作為廊橋都是最優的，我們可以預處理出這個值，然後枚舉分給國内航班的廊橋就可以了。

預處理的時候可以用平衡樹來優化。

算法複雜度 \(\Theta\left(n\log n\right)\)。

代碼：