P4652 童程算法大赛-全国公开赛（基础）

解题思路

题目要求按总成绩从高到低排名，成绩相同的人要保持输入顺序输出。这叫做"稳定排序"。人数最多 50 万，如果排序不稳定，相同分数的同学顺序就可能被打乱，导致答案错误。

我们用结构体 Stu 来保存每个同学的姓名 name、成绩 score，以及一个额外的编号 idx 表示他是第几个输入进来的。排序的比较函数写得很关键：先比分数，分数大的排前面；如果分数一样，就比 idx，idx 小的排前面。这样一来，成绩相同的人一定按输入顺序输出，等价于稳定排序。

称号的判断也容易出错，要仔细看区间：0 分是 Bad；1~199 分是 Not good（包含 1 分，不包含 200 分）；200~299 分是 Bronze medal（包含 200 分，不包含 300 分）；300~399 分是 Silver medal（包含 300 分，不包含 400 分）；400 分及以上是 Gold medal。可以按顺序写 if-else 判断：分数等于 0 就输出 Bad，小于 200 就输出 Not good，小于 300 就输出 Bronze medal，小于 400 就输出 Silver medal，否则输出 Gold medal。

因为 n 最大 50 万，输入输出量非常大，一定要加上 ios::sync_with_stdio(false) 和 cin.tie(0) 来加速读写，并且用 '\n' 而不是 endl 来换行，否则频繁刷新缓冲区会超时。这一点在数据大的题目里非常重要。

对照样例感受一下：Chenyao 考了 0 分，称号是 Bad；XTT 420 分、LZX 500 分都在 400 分以上，所以都是 Gold medal。输出时先输出分数最高的 LZX，再是 XTT，最后是 Chenyao，完全符合从高到低的顺序。如果两个同学分数相同，比如都是 420 分，谁先输入谁就先输出，这正是 idx 编号起到的作用。

参考代码

// P4652 童程算法大赛-全国公开赛：按成绩从大到小稳定排序并输出称号
#include <iostream>
#include <algorithm>
using namespace std;

struct Stu {
    char name[25];
    int score;
    int order; // 输入顺序，用于成绩相同时保持原顺序
} s[500005];

// 比较函数：成绩大的在前，成绩相同按输入顺序
bool cmp(const Stu &a, const Stu &b) {
    if (a.score != b.score) return a.score > b.score;
    return a.order < b.order;
}

// 根据分数返回称号
const char* title(int p) {
    if (p == 0) return "Bad";
    if (p < 200) return "Not good";
    if (p < 300) return "Bronze medal";
    if (p < 400) return "Silver medal";
    return "Gold medal";
}

int main() {
    ios::sync_with_stdio(false); // 加快输入输出，避免大数据超时
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i].name >> s[i].score;
        s[i].order = i;
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < n; i++) {
        cout << s[i].name << " " << s[i].score << " " << title(s[i].score) << '\n';
    }
    return 0;
}

复杂度分析

主要耗时在 sort 排序，时间复杂度 O(n log n)。n=50 万时，log2(50万)≈19，大约需要一千万次比较，配合快速 I/O 可以在一秒内通过。空间上存了 n 个结构体，每个约 33 字节，50 万个大约 16 MB，在内存限制范围内。