队列套队列求助
查看原帖
队列套队列求助
323183
CLCK楼主2022/10/27 15:45

如题,思路应该非常好懂,求助哪里写挂了

虽然STL超多但是毕竟开了O2

#include <iostream>
#include <queue>
using namespace std;
int n, m1, m2;
int ans = 0;
struct dep { //存飞机
	int a, b;
} p1[500005], p2[500005];
int main() {
	cin >> n >> m1 >> m2; //读入
	for (int i = 0; i < m1; i++) {
		cin >> p1[i].a >> p1[i].b;
	}
	for (int i = 0; i < m2; i++) {
		cin >> p2[i].a >> p2[i].b;
	}
	for (int i = 0; i <= n; i++) { //开始枚举廊桥数量
		int in = i, out = n - i;
		queue<queue<dep> > inside; //国内的廊桥队列
		int cnt1 = 0, cnt2 = 0, tmpans = 0;
		for (int j = 0; j < m1; j++) {
			if (cnt1 >= in || j == m1 - 1) { //如果廊桥满了/飞机没了
				while (!inside.empty()) { //遍历pop掉廊桥
					queue<dep> tmp = inside.front();
					inside.pop();
					while (!tmp.empty()) { //遍历pop掉廊桥中飞机并计数
						tmp.pop();
						tmpans ++;
					}
				}
				break; //统计答案
			}
			bool flag = false; //记录飞机是否找到现成的廊桥
			for (int k = 0; k < cnt1; k++) {
				if (inside.empty()) break; //如果有现成的廊桥序列
				queue<dep> npos = inside.front(); //从第一个廊桥开始遍历
				inside.pop();
				if (p1[j].a >= npos.back().b && !flag) { //如果能用则用
					npos.push(p1[j]);
					flag = true;
				}
				inside.push(npos); //push回去(为了保证顺序需要全部pop后push
			}
			if (flag) continue;
			queue<dep> nw; cnt1++; //如果没有能放的则再开一个廊桥
			nw.push(p1[j]);
			inside.push(nw); //放进去
		}
		queue<queue<dep> > outside; //国外的 具体思路与国内相同
		for (int j = 0; j < m2; j++) {
			if (cnt2 >= out || j == m2 - 1) {
				while (!outside.empty()) {
					queue<dep> tmp = outside.front();
					outside.pop();
					while (!tmp.empty()) {
						tmp.pop();
						tmpans ++;
					}
				}
				break;
			}
			bool flag = false;
			for (int k = 0; k < cnt2; k++) {
				if (outside.empty()) break;
				queue<dep> npos = outside.front();
				outside.pop();
				if (p2[j].a >= npos.back().b && !flag) {
					npos.push(p2[j]);
					flag = true;
				}
				outside.push(npos);
			}
			if (flag) continue;
			queue<dep> nw; cnt2++;
			nw.push(p2[j]);
			outside.push(nw);
		}
		ans = max(ans, tmpans); //记录答案
	}
	cout << ans << endl; //输出
	return 0;
}
2022/10/27 15:45
加载中...