part 1:
题目描述：
当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。
机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。
L 市新建了一座机场，一共有 \(n\) 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻，请你负责将 \(n\) 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。
输入格式
输入的第一行，包含三个正整数 \(n, m_1, m_2\)，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。
接下来 \(m_1\) 行，是国内航班的信息，第 \(i\) 行包含两个正整数 \(a_{1, i}, b_{1, i}\)，分别表示一架国内航班飞机的抵达、离开时刻。
接下来 \(m_2\) 行，是国际航班的信息，第 \(i\) 行包含两个正整数 \(a_{2, i}, b_{2, i}\)，分别表示一架国际航班飞机的抵达、离开时刻。
每行的多个整数由空格分隔。
输出格式
输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。
样例输入 #1
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
样例输出 #1
7
样例输入 #2
2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10
样例输出 #2
4
part 2
解析：
首先得以想到的是枚举所有可能，选择最优方案，这样的话时间复杂度约为 \(O(n^2)\) 在 \(n<=10^5\) 的情况下会超时。那么要怎么优化呢？
不妨这样想，一共有 \(n\) 个廊桥，如果给国内长区分 \(i (i<=n)\) 个，那么国际区就可以分到 \(n-i\) 个。那么就可以定义 \(f_i , g_i\) 分别为当分 \(i\) 个廊桥时能分到的廊桥个数。那么题目就转为求 \(f_i+g_{n-i}\) 的最大值。所以解题思路为：当有飞机抵达机场时如果还有空余的廊桥，则选择编号最小的一个停放，并使其廊桥贡献值加一。由于每当抵达机场时都要对廊桥编号进行排序，会占用大量时间，所以可以用堆来存放，最后用前缀和计算前 \(1-n\) 项和即可。
参考代码
#include<bits/stdc++.h>
#define bool char //防盗水印
using namespace std;
const int N = 1e6+5;
int n,m1,m2,f[N]={0},g[N]={0};
struct edge
{
int be,en;
}a[N],b[N];
struct node
{
int num,leave_t;
node(){}
node(int numm,int lea){num=numm;leave_t=lea;}
bool operator < (const node& r) const
{
return leave_t>r.leave_t;
}
};
bool cmp(edge x,edge y){return x.be<y.be;}
int main()
{
scanf("%d%d%d",&n,&m1,&m2);
for(int i = 1;i<=m1;i++)
scanf("%d%d",&a[i].be,&a[i].en);
for(int i = 1;i<=m2;i++)
scanf("%d%d",&b[i].be,&b[i].en);
sort(a+1,a+1+m1,cmp);
sort(b+1,b+1+m2,cmp);
priority_queue<int, vector<int> ,greater<int> > p; //存放空余的廊桥
priority_queue<node> pq; //存放停在廊桥飞机的廊桥编号和离开时间
for(int i = 1;i<=n;i++) p.push(i); //初始所有廊桥均为空闲状态
for(int i = 1;i<=m1;i++)
{
while(!pq.empty()&&a[i].be>pq.top().leave_t){
p.push(pq.top().num);
pq.pop();
}
if(!p.empty())
{
pq.push(node(p.top(),a[i].en));
f[p.top()]++;
p.pop();
}
}
while(!p.empty()) p.pop(); //清空队列，优先队列不支持 clear()
while(!pq.empty()) pq.pop();
for(int i = 1;i<=n;i++) p.push(i);
for(int i = 1;i<=m2;i++)
{
while(!pq.empty()&&b[i].be>pq.top().leave_t){
p.push(pq.top().num);
pq.pop();
}
if(!p.empty())
{
pq.push(node(p.top(),b[i].en));
g[p.top()]++;
p.pop();
}
}
for(int i = 2;i<=n/*千万别写成m1*/;i++) f[i]=f[i]+f[i-1];
for(int i = 2;i<=n/*千万别写成m2*/;i++) g[i]=g[i]+g[i-1];
int ans=0;
for(int i = 0;i<=n;i++)
ans=max(ans,f[i]+g[n-i]);
printf("%d",ans);
return 0;
}