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)\)。

代码：