题解 P7913 [CSP-S 2021] 廊桥分配
SevenElevenThirteen
·
·
题解
提供一种 **仅使用普及知识点，不用优先队列、`set`、`pair`、线段树、树状数组、分块** 的做法。
[题目链接](https://www.luogu.com.cn/problem/P7913)
我们从样例 $1$ 入手。
观察图片，不难看出能共用一个廊桥的飞机一定是在时间上没有重叠的（例如上图国内航班第 $1,3, 5$ 架）。这启示我们将所有飞机不重不漏地分组，使得每个组内的飞机都可以用一个廊桥解决停靠问题。
由于国内航班和国际航班是各自独立的，在此只用国内航班说明。用 $arr_i$ 和 $lea_i$ 表示第 $i$ 架飞机的抵达、离开时刻，$id_i$ 表示第 $i$ 架飞机是否已被分组。首先将所有飞机按照抵达时间从小到大排序（下文所指均为排序后的飞机），然后从 $1$ 开始枚举飞机。
还是以样例 $1$ 为例，不妨把飞机 $1\;\left[ 1,5 \right]$ 分到第 $1$ 组，并把 $id_1$ 修改为 $1$。因为同组内飞机没有时间冲突，所以下一架可选飞机 $3\;\left[6,10\right]$、$4\;\left[9,14\right]$、$5\;\left[13,18\right]$。应该选哪一架呢？飞机遵循“先到先得”原则，贪心地想，当飞机 $3$ 降落时，至少有一座廊桥是空闲的（即飞机 $1$ 使用的），而它在哪里停靠都是一样的，因此把它和飞机 $1$ 分为一组不会改变答案。推广一下，假设飞机 $i$ 已经被分组，同组内的下一架应是所有满足 $arr_x > lea_i \; \land \; id_x = 0$ 中抵达时间最早的。由于事先已将飞机排序，可以用二分找出第一架抵达时间晚于 $lea_i$ 的飞机 $x$。不断重复这一过程，如果没有飞机可选，则这一组已经分完。
注意到 $id$ 数组并没有单调性，即有可能 $id_x \ne 0$。若从 $x$ 向后暴力枚举，复杂度可能退化成 $O\left(n^2\right)$，显然无法接受。我们借用并查集的路径压缩思想来巧妙地解决这一问题。定义 $c_i$ 为第一架降落时间晚于 $arr_i$ 且没有组的飞机编号，初始时 $c_i \gets i + 1$。重复执行 $x \gets c_x$，直到 $id_x = 0$，开一个 `vector` 存储所有经过的飞机编号。对于 `vector` 中的每个数 $num$，把 $c_{num} \gets c_x$，这样下次查找时就会跳过没用的飞机。（$\texttt{Upd}$：其实这就是并查集，此部分复杂度 $O\left( n\log n \right)$。当然你也可以同时使用路径压缩和按秩合并，复杂度几乎线性。）
假设我们已经分好组，如果你认为从中选择飞机数最多的 $n$ 个组即为答案，那就大错特错了。回顾算法流程，组与组之间其实有着时间上的先后。回到样例，第 $1,3,5$ 架为第一组，第 $2,4$ 架为第二组。若此时只有一个廊桥，则第二组是用不上的，因为飞机 $1$ 已经占用了！我们不用排序，直接处理出前 $i$ 个国内/国际航班的组的前缀和 $s_1,\,s_2$，答案为 $\max\left\{s_{1_i} + s_{2_{n - i}}\right\}$。
以下为考场代码。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5;
int n,m1,m2;
struct Node{
int arr,lea,id;
void read()
{
scanf("%d%d",&arr,&lea);
return ;
}
bool operator < (const Node& x) const
{
return arr < x.arr;
}
}a[N + 5],b[N + 5];
int g1[N + 5],g2[N + 5],top1,top2;//g1 : 国内航班 g2 : 国际航班
int c[N + 5];
int nxta(int x)//二分+路径压缩
{
int l = 1,r = m1,res = -1;
while (l <= r)
{
int mid = (l + r) >> 1;
if (a[mid].arr >= x)
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (res < 0) return res;
vector<int> upd;
while (res > 0 && a[res].id != 0)
{
upd.push_back(res);
res = c[res];
}
while (!upd.empty())
{
c[upd.back()] = c[res];
upd.pop_back();
}
return res;
}
void pre1()
{
for (int i = 1;i < m1;i++) c[i] = i + 1;
c[m1] = -1;//-1表示没有飞机
for (int i = 1;i <= m1;i++)
{
if (a[i].id != 0) continue;
a[i].id = 1;
int cnt = 1,x = a[i].lea + 1;
int pos = nxta(x);
while (pos > 0)
{
a[pos].id = 1;
x = a[pos].lea + 1;
cnt++;
pos = nxta(x);
}
top1++;
g1[top1] = cnt;
}
return ;
}
int nxtb(int x)
{
int l = 1,r = m2,res = -1;
while (l <= r)
{
int mid = (l + r) >> 1;
if (b[mid].arr >= x)
{
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (res < 0) return res;
vector<int> upd;
while (res > 0 && b[res].id != 0)
{
upd.push_back(res);
res = c[res];
}
while (!upd.empty())
{
c[upd.back()] = c[res];
upd.pop_back();
}
return res;
}
void pre2()
{
for (int i = 1;i < m2;i++) c[i] = i + 1;
c[m2] = -1;
for (int i = 1;i <= m2;i++)
{
if (b[i].id != 0) continue;
b[i].id = 1;
int cnt = 1,x = b[i].lea + 1;
int pos = nxtb(x);
while (pos > 0)
{
b[pos].id = 1;
x = b[pos].lea + 1;
cnt++;
pos = nxtb(x);
}
top2++;
g2[top2] = cnt;
}
return ;
}
int s1[N + 5],s2[N + 5];
void calc()
{
for (int i = 1;i <= n;i++)
{
s1[i] = s1[i - 1] + g1[i];
}
for (int i = 1;i <= n;i++)
{
s2[i] = s2[i - 1] + g2[i];
}
return ;
}
int main()
{
freopen("airport.in","r",stdin);
freopen("airport.out","w",stdout);
scanf("%d%d%d",&n,&m1,&m2);
for (int i = 1;i <= m1;i++)
{
a[i].read();
}
for (int i = 1;i <= m2;i++)
{
b[i].read();
}
sort(a + 1,a + m1 + 1);
sort(b + 1,b + m2 + 1);
pre1();
pre2();
calc();
int ans = 0;
for (int i = 0;i <= n;i++)
{
ans = max(ans,s1[i] + s2[n - i]);
}
printf("%d\n",ans);
return 0;
}
```