如题,思路应该非常好懂,求助哪里写挂了
虽然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;
}