P4620 倒数第一名（入门）

解题思路

这道题要找出英语成绩最低、而且并列时最先出现的那位同学。可以用"老师巡堂"的办法，分四步。

第一步，把任务想清楚。 全班同学排成一列，老师从队首走到队尾，手里攥着一张"目前最差记录"。每走到一位同学，就看看他的成绩是不是比手里的记录还低：更低就把名字记下来；一样高或者更高就不换人。因为只有"更差"才换人，所以分数相同的后来者不会把先来者挤掉，最后留下的一定是"分数最低且最先出现"的同学。

第二步，用一个例子验证思路。 前两位同学都考 60 分，老师记下第一位；第三位考 50 分，比 60 更差，换成第三位；第四位又考 50 分，和当前记录一样，不换。最后输出的就是第三位，也就是 50 分里最先出现的那位。注意全程只有一个"严格更低才更新"，这是并列时保靠前者的关键。

第三步，用结构体打包信息。 学号、姓名、成绩三样信息用结构体装在一起，整体赋值和比较都方便。姓名是字符串，用字符数组保存。

第四步，注意初始值和输出格式。 成绩范围是 0 到 100，一开始把记录设成 101，这样无论第一位同学考多少分都比它低，保证第一次比较就能选中第一位同学。如果初始值设成 0，考 0 分的同学反而选不上，设成 101 更稳妥。最后输出学号和姓名，中间用空格隔开，记得换行。

回顾总结。"找最差"和"找最好"其实是一对好兄弟，区别只在比较符号相反。用结构体保存当前最差记录，用"严格更差才更新"保证并列时保留先出现者，再把初始记录设成范围外的数 101，四步搞定。

参考代码

// 用途：找出英语成绩最低且最先出现的学生。
#include <iostream>
using namespace std;

struct Student {
    int id;             // 学生的学号
    char name[101];     // 学生的姓名
    int score;          // 学生的英语成绩
};

int main() {
    int n;              // 学生人数
    cin >> n;           // 读入学生人数

    Student lastPlace;      // 保存目前倒数第一名的信息
    lastPlace.score = 101;  // 成绩最大为100，先放一个更大的数

    for (int i = 0; i < n; i++) {               // 依次读入每个学生
        Student current;                        // 当前学生的信息
        cin >> current.id >> current.name >> current.score;  // 读入学号、姓名和成绩
        if (current.score < lastPlace.score) {  // 当前成绩更低时更新答案
            lastPlace = current;                // 保存当前学生
        }
    }

    cout << lastPlace.id << ' ' << lastPlace.name << endl;  // 输出学号和姓名
    return 0;                                   // 程序结束
}

复杂度分析

程序从头到尾把 n 个学生各读一遍、比较一遍，所以时间复杂度是 O(n)。这里 n 小于 1000，运行飞快，即使数据达到上限也只在一瞬间完成。程序只用了几个变量和一个结构体变量来保存"当前最差"的学生，额外空间是 O(1)，不会随学生人数增长，无论 100 人还是 1000 人，用到的空间都一样少。