问题分析

本题需要将 $n$ 个廊桥合理分配给国内区和国际区，使得能够停靠廊桥的飞机总数最大化。关键在于廊桥使用遵循"先到先得"原则，需要高效模拟廊桥的分配过程。

核心思路

算法框架：预处理 + 前缀和优化

• 分别处理国内和国际航班，计算当分配 $k$ 个廊桥时能服务的飞机数量

• 使用优先队列模拟廊桥分配过程

• 通过前缀和优化快速计算各种分配方案的结果

关键数据结构

typedef pair<int, int> P;  // (离开时间, 廊桥编号)
priority_queue<P, vector<P>, greater<P>> que1;  // 小根堆，维护正在使用的廊桥
priority_queue<int, vector<int>, greater<int>> que2;  // 小根堆，维护空闲廊桥编号

算法步骤

1.预处理函数 calc

void calc(node *t, int m, int *res) {
    priority_queue<P, vector<P>, greater<P>> que1;  // 正在使用的廊桥
    priority_queue<int, vector<int>, greater<int>> que2;  // 空闲廊桥
    
    // 初始化所有廊桥为空闲状态
    for (int i = 1; i <= n; i++) {
        que2.push(i);
    }
    
    // 按抵达时间处理每架飞机
    for (int i = 1; i <= m; i++) {
        // 释放已离开的廊桥
        while (!que1.empty() && t[i].x >= que1.top().first) {
            que2.push(que1.top().second);
            que1.pop();
        }
        
        // 分配空闲廊桥
        if (!que2.empty()) {
            int p = que2.top();  // 选择编号最小的空闲廊桥
            que2.pop();
            res[p]++;  // 记录第p个廊桥服务的飞机数
            que1.push({t[i].y, p});  // 廊桥被占用直到飞机离开
        }
    }
    
    // 计算前缀和：res[i]表示分配i个廊桥能服务的飞机总数
    for (int i = 1; i <= n; i++) {
        res[i] += res[i - 1];
    }
}

2.主算法流程

int main() {
    // 读入数据
    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, comp);
    sort(b + 1, b + m2 + 1, comp);
    
    // 分别计算国内和国际航班的廊桥使用情况
    calc(a, m1, res1);  // res1[i]: 国内区分配i个廊桥能服务的飞机数
    calc(b, m2, res2);  // res2[i]: 国际区分配i个廊桥能服务的飞机数
    
    // 枚举所有分配方案，求最大值
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, res1[i] + res2[n - i]);
    }
    cout << ans << "\n";
    return 0;
}

算法正确性证明

1.贪心策略正确性

按抵达时间排序：满足"先到先得"原则

选择编号最小的空闲廊桥：不影响后续分配的最优性

及时释放廊桥：确保资源充分利用

2.前缀和优化正确性

res[k] 表示分配 $k$ 个廊桥时能服务的飞机总数

通过前缀和累加：$res[i] = \sum_{j=1}^{i} res[j]$

复杂度分析

时间复杂度

• 排序：$O(m_1 \log m_1 + m_2 \log m_2)$

• 模拟分配：$O((m_1 + m_2) \log n)$

• 枚举分配方案：$O(n)$

总复杂度：$O((m_1 + m_2) \log n)$

空间复杂度

$O(n + m_1 + m_2)$

关键优化点

双优先队列：高效管理廊桥的分配和释放

前缀和预处理：$O(1)$ 时间查询任意分配方案的结果

分别处理：国内和国际航班互不影响，可独立计算

样例分析

以样例1为例：

国内航班：5架，国际航班：4架

当分配方案为 (国内2个，国际1个) 时：

国内区服务飞机数：res1[2] = 4

国际区服务飞机数：res2[1] = 3

总计：$4 + 3 = 7$

总结

本题通过巧妙的优先队列模拟和前缀和优化，在 $O((m_1 + m_2) \log n)$ 时间内解决了廊桥分配问题。算法充分利用了"先到先得"的规则特性，通过贪心策略保证了最优性，是优先队列应用的经典范例。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int res1[N], res2[N];
typedef pair<int, int> P;
int n;

struct node {
    int x, y;
} a[N], b[N];

int comp(node a, node b) {
    if (a.x == b.x) {
        return a.y < b.y;
    }

    return a.x < b.x;
}

void calc(node *t, int m, int *res) {
    priority_queue<P, vector<P>, greater<P>> que1;
    priority_queue<int, vector<int>, greater<int>> que2;

    for (int i = 1; i <= n; i++) {
        que2.push(i);
    }

    for (int i = 1; i <= m; i++) {
        while (!que1.empty() && t[i].x >= que1.top().first) {
            que2.push(que1.top().second);
            que1.pop();
        }

        if (!que2.empty()) {
            int p = que2.top();
            que2.pop();
            res[p]++;
            que1.push({t[i].y, p});
        }
    }

    for (int i = 1; i <= n; i++) {
        res[i] += res[i - 1];
    }
}

int main() {
    //freopen("airport.in", "r", stdin);
    //freopen("airport.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0);
    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, comp);
    sort(b + 1, b + m2 + 1, comp);
    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 << "\n";
    return 0;
}