CSP-S2021 廊桥分配 题解

题意

有 $n$ 个廊桥，要分成两组。

有两组飞机，如果该组有空廊桥就停靠廊桥，否则不管。

求廊桥分配给两组后能停靠廊桥的飞机的最大数目。

分析

首先对飞机按到达顺序排序。

我们先不考虑廊桥的数目，只考虑分配的问题。

显然有以下的贪心：

• 如果之前的廊桥有空闲的，那么找到编号最小的廊桥，将这架飞机安排过去；

• 否则新开一个廊桥，将这架飞机分配给他。

找到每个飞机分配的廊桥后，我们开个桶计算每个廊桥分配了多少架飞机，再前缀和一下就能知道分配 $i$ 个廊桥最多能停靠多少架飞机。

最后把两个区的答案匹配起来取 Max 即可。

那么我们的问题就转变为了对于每一个飞机，如何快速求得他应该分配给哪个廊桥。显然需要数据结构维护。

提供两种思路：

• 我们把每架安排好的飞机按离开顺序放进小根堆里，同时再开一个小根堆记录空闲的廊桥。对于当前枚举到的这架飞机，我们先把已经离开的飞机弹出小根堆，同时更新空闲的廊桥；最后把空闲廊桥的堆顶分配给这架飞机。

• 我们按照廊桥建线段树，每个位置表示该区间最早离开的时间。对于每架飞机，如果左区间的最小值小于该飞机到达的时间就走左区间，否则走右区间，到达叶子直接更新答案即可。