解题思路

演唱会要从 n 首歌里选出欢乐值最大的 m 首。题目的要求是：按欢乐值从大到小排序后，输出前 m 首的编号。

注意这里有个小坑：我们要输出的不是欢乐值，而是歌曲的编号。编号是按照输入顺序从 1 到 n 的。

打个比方：就像班里按成绩排名，我们要的不是成绩，而是学号。

做法可以分成两步：

1. 排序：用"选择排序"，把欢乐值从大到小排好。每次找出剩下里面欢乐值最大的一首，放到前面。
2. 编号一起移动：欢乐值交换位置的时候，对应的编号也要跟着换。这样排完序后，编号数组的前 m 个就是歌单。

选择排序的原理很像"挑选手足"：先在整个队伍里找出个子最高的站到第1位，再从剩下的人里找出最高的站到第2位……一直选到第 m 位。

参考代码

// P4601 演唱会：按欢乐值从大到小排序，输出前m首歌的编号
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int h[1005], id[1005];
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        id[i] = i;  // 编号按照输入顺序：1~n
    }
    // 选择排序：欢乐值大的往前放
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (h[j] > h[i]) {
                swap(h[i], h[j]);     // 交换欢乐值
                swap(id[i], id[j]);   // 编号跟着欢乐值一起换
            }
        }
    }
    // 输出欢乐值最大的前m首的编号
    for (int i = 1; i <= m; i++) {
        cout << id[i];
        if (i < m) cout << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

• 选择排序要拿每一首歌和它后面所有歌都比较一遍：第1首和后面 n-1 首比，第2首和后面 n-2 首比……总共大约比较 n×(n-1)/2 次，所以时间复杂度是 O(n²)。
• 我们用两个数组 h 和 id 各存 n 个数，空间复杂度是 O(n)。

当 n 比较大的时候 O(n²) 会比较慢，但本题 n 的范围不大，用选择排序完全够用。