简答题
偏难
#22120
1、廊桥分配
1、廊桥分配



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e5 + 5;
struct e {
int st, ed;
} a[Maxn];
bool cmp(e x, e y) {
return x.st < y.st;
}
priority_queue<int> hp_id;
priority_queue<pair<int, int>> hp_ed;
int n, m1, m2, ca[Maxn], cb[Maxn];
int main() {
scanf("%d%d%d", &n, &m1, &m2);
for (int i = 1; i <= m1; ++i) {
scanf("%d%d", &a[i].st, &a[i].ed);
}
sort(a + 1, a + m1 + 1, cmp);
for (int i = 1; i <= n; ++i) {
hp_id.push(-i);
}
for (int i = 1; i <= m1; ++i) {
if (!hp_ed.empty()) {
while (-hp_ed.top().first < a[i].st) {
hp_id.push(-hp_ed.top().second);
hp_ed.pop();
if (hp_ed.empty()) {
break;
}
}
}
if (!hp_id.empty()) {
int x = -hp_id.top();
hp_id.pop();
ca[x]++;
hp_ed.push(make_pair(-a[i].ed, x));
}
}
for (int i = 1; i <= n; ++i) {
ca[i] += ca[i - 1];
}
while (!hp_ed.empty()) {
hp_ed.pop();
}
while (!hp_id.empty()) {
hp_id.pop();
}
for (int i = 1; i <= m2; ++i) {
scanf("%d%d", &a[i].st, &a[i].ed);
}
sort(a + 1, a + m2 + 1, cmp);
for (int i = 1; i <= n; ++i) {
hp_id.push(-i);
}
for (int i = 1; i <= m2; ++i) {
if (!hp_ed.empty()) {
while (-hp_ed.top().first < a[i].st) {
hp_id.push(-hp_ed.top().second);
hp_ed.pop();
if (hp_ed.empty()) {
break;
}
}
}
if (!hp_id.empty()) {
int x = -hp_id.top();
hp_id.pop();
cb[x]++;
hp_ed.push(make_pair(-a[i].ed, x));
}
}
for (int i = 1; i <= n; ++i) {
cb[i] += cb[i - 1];
}
int mx_ans = 0;
for (int i = 0; i <= n; ++i) {
mx_ans = max(mx_ans, ca[i] + cb[n - i]);
}
printf("%d", mx_ans);
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#include <bits/stdc++.h>
using namespace std;
// 计算某类航班(国内或国际)分配bridgeNum个廊桥时,能停靠的最大飞机数
int countPlanes(vector<pair<int, int>>& flights, int bridgeNum) {
if (bridgeNum == 0) return 0;
sort(flights.begin(), flights.end()); // 按到达时间升序排序
// used: 存储(离开时间, 廊桥编号),小根堆(按离开时间排序,便于释放过期廊桥)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> used;
// idle: 存储空闲廊桥编号,小根堆(便于分配最小编号的空闲廊桥)
priority_queue<int, vector<int>, greater<>> idle;
for (int i = 1; i <= bridgeNum; ++i) {
idle.push(i);
}
int res = 0;
for (auto& flight : flights) {
int arrTime = flight.first, depTime = flight.second;
// 释放所有离开时间 <= 当前航班到达时间的廊桥(将这些廊桥加入空闲队列)
while (!used.empty() && used.top().first <= arrTime) {
idle.push(used.top().second);
used.pop();
}
// 若有空闲廊桥,分配给当前航班
if (!idle.empty()) {
int bridgeId = idle.top();
idle.pop();
used.push({depTime, bridgeId});
res++;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m1, m2;
cin >> n >> m1 >> m2;
vector<pair<int, int>> domestic, international;
// 读取国内航班信息
for (int i = 0; i < m1; ++i) {
int a, b;
cin >> a >> b;
domestic.emplace_back(a, b);
}
// 读取国际航班信息
for (int i = 0; i < m2; ++i) {
int a, b;
cin >> a >> b;
international.emplace_back(a, b);
}
// 计算国内分配0~n个廊桥时的最大停靠数
vector<int> ca(n + 1);
for (int i = 0; i <= n; ++i) {
ca[i] = countPlanes(domestic, i);
}
// 计算国际分配0~n个廊桥时的最大停靠数
vector<int> cb(n + 1);
for (int i = 0; i <= n; ++i) {
cb[i] = countPlanes(international, i);
}
// 枚举所有分配方案,找到最大值
int maxAns = 0;
for (int i = 0; i <= n; ++i) {
maxAns = max(maxAns, ca[i] + cb[n - i]);
}
cout << maxAns << endl;
return 0;
}</pre><p><br/></p>
这道题暂未补解析。