1

噢莫加纳加加加  •  2个月前


#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;

struct range { //结构体存航班到达时间和离开时间
	int x, y;
} a[100005], b[100005]; //国内航班和国际航班

typedef pair<int, int>pii; //定义一个类型,表示一个整数对

int res1[100005], res2[100005];//结果

bool cmp(const range &a, const range &b) {
	return a.x < b.x ;
}

void calc(range *t, int m, int *res) {
	priority_queue<pii, vector<pii>, greater<pii> > lq;
	priority_queue<int, vector<int>, greater<int> > wq;
	for (int i = 1; i <= n; i++) {
		wq.push(i);
	}
	for (int i = 1; i <= m; i++) {
		while (!lq.empty() && t[i].x >= lq.top().first) {
			wq.push(lq.top().second);
			lq.pop();
		}
		if (wq.empty())
			continue;
		int dest = wq.top();
		wq.pop();
		res[dest]++;//桶排
		lq.push(make_pair(t[i].y, dest));
	}
	for (int i = 1; i <= n; i++) {
		res[i] += res[i - 1];
	}

}

int main() {
	int m1, m2;
	cin >> n >> m1 >> m2;
	//读入航班到达时间、离开时间
	for (int i = 1; i <= m1; i++) {
		cin >> a[i].x >> a[i].y;
	}
	for (int i = 1; i <= m2; i++) {
		cin >> b[i].x >> b[i].y;
	}
	//对国内航班和国际航班进行排序
	sort(a + 1, a + m1 + 1, cmp);
	sort(b + 1, b + m2 + 1, cmp);
	//计算两个航班列表的结果
	calc(a, m1, res1);
	calc(b, m2, res2);
	//计算最大空闲廊桥数量
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		ans = max(ans, res1[i] + res2[n - i]);
	}
	cout << ans << endl;
	return 0;
}

评论:

请先登录,才能进行评论