CSP2021重做-廊桥分配

#include <queue>
#include <utility>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 1e5 + 5;
typedef std::pair<int, int> PII;
PII a[N], b[N]; int n, ma, mb, suma[N], sumb[N], res;
void solve(int m, std::pair<int, int> p[N], int *sump) {
	std::priority_queue<PII, std::vector<PII>, std::greater<PII> > heap1, heap2;
	// heap: [停机场,离开时间] heap1: first=离开时间, heap2: first=停机场
	int tot = 0;
	for(int i = 1; i <= m; i ++) {
		while(heap1.size() && heap1.top().first < p[i].first) // 将所有的之前离开的放入可使用队列
			heap2.push({heap1.top().second, heap1.top().first}), heap1.pop();
		if(heap2.empty()) // 新开一个
			sump[++ tot] = 1, heap1.push({p[i].second, tot});
		else // 尽量放入编号小的
			sump[heap2.top().first] ++, heap1.push({p[i].second, heap2.top().first}), heap2.pop();
	}
	for(int i = 1; i <= n; i ++) sump[i] += sump[i - 1]; // 累计所有飞机
}
int main() {
// 	freopen("airport.in", "r", stdin);
// 	freopen("airport.out", "w", stdout);
	scanf("%d%d%d", &n, &ma, &mb);
	for(int i = 1; i <= ma; i ++) scanf("%d%d", &a[i].first, &a[i].second);
	for(int i = 1; i <= mb; i ++) scanf("%d%d", &b[i].first, &b[i].second);
	std::sort(a + 1, a + ma + 1), std::sort(b + 1, b + mb + 1), solve(ma, a, suma), solve(mb, b, sumb);
	for(int i = 0; i <= n; i ++) res = std::max(res, suma[i] + sumb[n - i]);
	printf("%d\n", res), fclose(stdin), fclose(stdout);
	return 0;
}