PAT天梯赛L2真题精讲：从‘赛场安排’问题看如何优化C++代码的时间和空间

在算法竞赛中，能够解决问题只是第一步，真正考验选手水平的是如何写出高效、优雅的代码。今天我们就以PAT天梯赛L2级别的"赛场安排"问题为例，深入探讨C++代码的优化之道。这个问题看似简单，但其中蕴含着许多值得深思的优化点，特别适合已经掌握基础解法但希望提升代码质量的进阶开发者。

1. 问题分析与原始解法评估

让我们先理解题目要求：我们需要将多所学校的参赛学生安排到容量为C的赛场中，要求每个赛场的学生不超过容量C，同时最小化每个学校需要联系的监考老师数量（即最小化每个学校学生分布的赛场数量）。

原始解法采用了以下策略：

1. 对于每个学校，首先计算其需要的完整赛场数量（x/c）
2. 将余数部分（x%c）放入优先队列（大顶堆）
3. 最后尝试将这些余数部分填充到已有的赛场中

// 原始代码关键部分
while (!Q.empty()) {
    x = Q.top(), Q.pop();
    bool flag = true;
    for (int i = 0; i < cnt; ++i) {
        if (a[i] + x <= c) {
            a[i] += x, flag = false;
            break;
        }
    }
    if (flag) a[cnt++] = x;
}

这个解法虽然正确，但存在明显的性能隐患。最坏情况下，当所有学校的余数都无法互相填充时，内层循环会遍历所有已存在的赛场，时间复杂度可能达到O(N^2)。考虑到N的最大值是5000，这在最坏情况下会有2500万次操作，虽然现代计算机能够处理，但在竞赛环境中可能成为瓶颈。

2. 优化方向一：数据结构的选择

原始解法使用数组存储赛场剩余容量，查找可用赛场采用线性扫描。我们可以考虑更高效的数据结构：

2.1 使用有序集合优化查找

C++的 set 或 multiset 可以维护有序的赛场剩余容量，实现快速查找：

multiset<int> available_rooms;

while (!Q.empty()) {
    x = Q.top(); Q.pop();
    auto it = available_rooms.lower_bound(x);
    if (it != available_rooms.end()) {
        int room = *it;
        available_rooms.erase(it);
        if (room > x) {
            available_rooms.insert(room - x);
        }
    } else {
        available_rooms.insert(c - x);
    }
}

这种方法将查找时间从O(N)降低到O(logN)，整体复杂度从O(N^2)降到O(NlogN)。

2.2 利用题目特性进行优化

注意到题目中C的范围是10≤C≤50，这个值域非常小，我们可以利用这一点：

1. 使用计数数组记录不同剩余容量的赛场数量
2. 查找时直接从当前余数开始向下查找

int room_count[51] = {0}; // 记录剩余容量为1-50的赛场数量

while (!Q.empty()) {
    x = Q.top(); Q.pop();
    bool found = false;
    for (int rem = x; rem <= c; ++rem) {
        if (room_count[rem] > 0) {
            room_count[rem]--;
            if (rem > x) {
                room_count[rem - x]++;
            }
            found = true;
            break;
        }
    }
    if (!found) {
        room_count[c - x]++;
    }
}

这种方法的时间复杂度是O(N*C)，由于C≤50，实际表现可能比O(NlogN)的set解法更好。

3. 优化方向二：数学计算的精炼

原始代码中使用了浮点数运算来计算赛场数量：

cout << s << " " << ceil(1.0 * x / c) << endl;

这在C++中其实可以完全用整数运算替代：

cout << s << " " << (x + c - 1) / c << endl;

这种写法不仅避免了浮点数运算的开销，还消除了可能的精度问题，是竞赛编程中的常用技巧。

4. 优化方向三：内存访问的优化

原始代码使用固定大小的数组 a[MAX_N] ，这在最坏情况下可能需要5000个元素的空间。考虑到C≤50，实际需要的赛场数量不会太多（因为每个赛场至少放置1人，最多需要总人数个赛场）。

我们可以采用更灵活的内存管理方式：

4.1 使用动态数组

vector<int> a;
a.reserve(1000); // 预分配合理大小

4.2 结合优先队列优化

实际上，我们可以完全避免使用数组，直接在优先队列中维护赛场剩余容量：

priority_queue<int> available_rooms;

while (!Q.empty()) {
    x = Q.top(); Q.pop();
    if (!available_rooms.empty() && available_rooms.top() >= x) {
        int room = available_rooms.top();
        available_rooms.pop();
        if (room > x) {
            available_rooms.push(room - x);
        }
    } else {
        available_rooms.push(c - x);
    }
}

这种方法既节省了内存，又保持了较好的时间复杂度（O(NlogN)）。

5. 综合优化方案与性能对比

结合上述优化思路，我们可以给出一个综合优化版本：

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, c, total_rooms = 0;
    cin >> n >> c;
    
    priority_queue<int> remainders;
    priority_queue<int> available_rooms;
    
    for (int i = 0; i < n; ++i) {
        string s;
        int x;
        cin >> s >> x;
        
        int rooms_needed = (x + c - 1) / c;
        cout << s << " " << rooms_needed << "\n";
        
        total_rooms += x / c;
        if (x % c != 0) {
            remainders.push(x % c);
        }
    }
    
    while (!remainders.empty()) {
        int x = remainders.top();
        remainders.pop();
        
        if (!available_rooms.empty() && available_rooms.top() >= x) {
            int room = available_rooms.top();
            available_rooms.pop();
            if (room > x) {
                available_rooms.push(room - x);
            }
        } else {
            available_rooms.push(c - x);
            total_rooms++;
        }
    }
    
    cout << total_rooms;
    return 0;
}

让我们对比一下各版本的性能：

优化方案	时间复杂度	空间复杂度	代码复杂度	适用场景
原始数组法	O(N^2)	O(N)	低	小规模数据
有序集合法	O(NlogN)	O(N)	中	通用
计数数组法	O(N*C)	O(C)	中	C值较小时
双优先队列法	O(NlogN)	O(N)	中	通用

在实际竞赛中，选择哪种优化方案需要考虑问题的具体约束条件。对于本题，由于C的范围很小（≤50），计数数组法可能是最优选择，它既保证了线性时间复杂度，又节省了内存空间。

6. 竞赛编程中的优化思维框架

通过这个案例，我们可以总结出竞赛编程中代码优化的通用思维框架：

1. 复杂度分析先行 ：在实现任何解法前，先分析最坏情况下的时间和空间复杂度
2. 数据结构选择 ：根据操作需求选择最适合的数据结构（查找多用set/map，频繁插入删除用list等）
3. 题目特性利用 ：特别关注题目中给出的数值范围等特殊条件
4. 数学简化 ：尽可能用整数运算替代浮点运算，用位运算替代算术运算
5. 内存管理 ：预估数据规模，避免不必要的内存分配
6. IO优化 ：在C++中使用 ios::sync_with_stdio(false); 和 cin.tie(nullptr); 加速输入输出

在实际比赛中，不必追求极致的优化，而应该在代码清晰度和执行效率之间找到平衡点。记住，可读性也是代码质量的重要组成部分。

7. 进一步优化与思考

虽然我们已经讨论了几种优化方案，但这个问题还有进一步探讨的空间：

7.1 贪心算法的正确性证明

原始解法采用了贪心算法，将人数最多的学校优先处理。我们需要思考：

• 为什么这种贪心策略是正确的？
• 是否存在反例会使这种策略失效？
• 如何严格证明这种贪心策略的最优性？

7.2 其他可能的解法

除了我们已经讨论的方法外，还可以考虑：

1. 二分答案法 ：二分搜索最少的赛场数量，检查是否可行
2. 网络流模型 ：将问题建模为最大流问题（虽然可能大材小用）
3. 动态规划 ：尝试定义状态表示和转移方程

7.3 实际应用中的扩展

如果考虑更复杂的现实场景，比如：

• 不同赛场有不同的容量
• 某些学校的学生需要分配到特定赛场
• 监考老师有额外的限制条件

这些扩展会使问题变得更加复杂，可能需要完全不同的解法。