P4622 马拉松比赛（基础）

解题思路

这道题要把 n 名运动员按成绩排序。规则有两条：第一，用时少的成绩好，排前面；第二，用时一样时，序号小的排前面。这里要注意，序号是字符串而不是数字，比如“075988”这样的序号，在字典序里字符 '0' 比 '1' 小，所以“075988”要排在“1”的前面，这与我们平时理解的数字大小不一样，一定要用字符串比较，不能用数字比较。strcmp 就是按字典序比较字符串的标准函数。

数据规模很大，n 最大到 100000，如果用手写的选择排序或冒泡排序，最坏情况要做大约 100 亿次比较，会超时。所以我们用 sort() 配合自定义比较函数来完成，sort() 是快速排序，处理 10 万条数据绰绰有余。比较函数里先比较用时，用时不同就按用时从小到大；用时相同就用 strcmp 按字典序比较序号。因为分钟数可能大到 10 亿，用时要用 long long 保存，用 int 可能会溢出；序号最多十几位，字符数组开 25 足够。数组比较大，声明成静态数组避免栈溢出。

参考代码

// 用途：按马拉松用时从少到多、序号从小到大排序后输出运动员序号。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct Runner {
    char id[25];        // 运动员的序号字符串
    long long time;     // 运动员跑完全程所用的分钟数
};

// 排序规则：用时少的排前面；用时相同，序号小的排前面（序号按字典序比较）
bool cmp(const Runner& x, const Runner& y) {
    if (x.time != y.time) return x.time < y.time;
    return strcmp(x.id, y.id) < 0;
}

int main() {
    int n;                              // 运动员人数
    cin >> n;                           // 读入运动员人数
    static Runner a[100005];            // 保存所有运动员信息，静态区避免栈溢出

    for (int i = 0; i < n; i++) {       // 读入每名运动员
        cin >> a[i].id >> a[i].time;    // 读入序号和用时
    }
    sort(a, a + n, cmp);                // 按规则排序

    for (int i = 0; i < n; i++) {       // 按排好顺序输出
        cout << a[i].id << '\n';        // 输出运动员序号
    }
    return 0;                           // 程序结束
}

复杂度分析

sort() 平均时间复杂度 O(n log n)，n 最大 100000，log n 约 17，总共约 170 万次操作，完全没问题。程序用一个结构体数组存所有运动员，空间 O(n)。如果换成冒泡排序就是 O(n²)，在 n 是 10 万时要做好几十亿次比较，会超时，这就是选择 sort() 的原因。再补充一点，如果用时相同的运动员序号长度不一样，比如“9”和“10”，字典序里“10”排在“9”前面（因为字符 '1' 小于 '9'），这与数字大小恰好相反，所以必须坚持用字符串比较，这正是本解法的关键。