解题思路

这道题要我们在读成绩的同时，记住最高分和最低分，以及它们分别是哪名同学。

我们用“打擂台”的思路：

• mx 记录目前出现的最高分，mxi 记录它的编号；
• mn 记录目前出现的最低分，mni 记录它的编号。

每读到一个新分数，就和擂台上的冠军比一比：

• 如果比 mx 还大，说明出现了新冠军，就更新 mx 和 mxi；
• 如果比 mn 还小，说明出现了新倒数第一，就更新 mn 和 mni。

因为题目保证每名学生的最终得分都不相同，所以不会出现最高分并列的情况，最后直接输出即可。

这种“边读边比较”的方法妙在：不需要先把所有分数存下来，读一个比一个，一趟就干完活。

参考代码

// P4452 童程好声音：一遍输入同时更新最高分和最低分，并记录对应的编号
#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    int mx = -1, mxi = 0;  // 最高分及其编号
    int mn = 101, mni = 0; // 最低分及其编号
    for (int i = 1; i <= n; i++) {
        cin >> x;                   // 第i名学生的得分
        if (x > mx) { mx = x; mxi = i; }   // 更新最高分
        if (x < mn) { mn = x; mni = i; }   // 更新最低分
    }
    cout << mx << " " << mxi << endl;   // 先输出最高分和编号
    cout << mn << " " << mni << endl;   // 再输出最低分和编号
    return 0;
}

复杂度分析

• 只从头到尾扫一遍所有分数，时间复杂度是 O(n)。
• 只用了一小把变量（mx、mn、mxi、mni），空间复杂度是 O(1)。