P4676 竞赛排名（基础）

解题思路

第一步，存好分数和编号。 分数和编号是绑定的，用两个数组 score 和 id 存。输入第 i 个分数时，把编号 id[i] 记成 i，编号从 1 到 n。

第二步，选择排序找最大。 每一轮从剩余的人里挑出分数最高的，放到这一轮的最前面。外层循环 i 从 1 到 n，内层循环 j 从 i+1 到 n 找最大的分数位置，用 maxIdx 记住位置，找到后把 score[i] 和 score[maxIdx] 交换。

第三步，同步交换编号。 交换分数时必须同时交换编号，否则分数就对不上人了！所以交换完分数，要立刻把 id[i] 和 id[maxIdx] 也交换。

第四步，输出前 5 名。 排完后数组前 5 个位置就是前 5 名，输出他们的编号，相邻编号之间用空格隔开，末尾换行。

想一想生活里的例子。 体育课上挑人：每一轮从剩下的人里挑出分数最高的，让他站到队伍前面。第一轮挑全场第一，第二轮挑剩余第一……挑完就是分数从高到低。

用例子验证。 假设 10 个人的分数依次是 5 8 9 1 2 7 6 4 3 10，选择排序挑出的前 5 名依次是 10 号（10 分）、3 号（9 分）、2 号（8 分）、6 号（7 分）、7 号（6 分），输出的编号就是 10 3 2 6 7。

边界情况： n 至少 10，每个人的分数都不相同，所以每一轮选出的最高分是唯一的，顺序确定。n ≤ 100，数组开 105 足够。

参考代码

// P4676 竞赛排名：按分数降序排序，输出前5名编号（用选择排序）
#include <iostream>
using namespace std;

int score[105]; // 分数
int id[105];    // 编号

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
        id[i] = i; // 编号从1到n
    }
    // 选择排序：每一轮把剩余中分数最高的放到前面
    for (int i = 1; i <= n; i++) {
        int maxIdx = i;
        for (int j = i + 1; j <= n; j++) {
            if (score[j] > score[maxIdx]) maxIdx = j; // 找出最大的
        }
        int temp = score[i]; score[i] = score[maxIdx]; score[maxIdx] = temp; // 交换分数
        temp = id[i]; id[i] = id[maxIdx]; id[maxIdx] = temp;                 // 交换编号
    }
    for (int i = 1; i <= 5; i++) { // 输出前5名的编号
        if (i > 1) cout << ' ';
        cout << id[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

选择排序是双重循环，外层跑 n 轮、内层找最大，时间复杂度 O(n²)，n ≤ 100，最多一万次操作，非常快。空间复杂度 O(n)，存分数和编号两个数组。