解题思路

题目要求：老师公布了 n 个同学的语文成绩，小明想知道自己的排名。

排名的规则是：名次 = 成绩比自己高的人数 + 1。

为什么要 +1 呢？我们想一想：

• 第 1 名：前面有 0 个人比他高，名次 = 0 + 1 = 1
• 第 2 名：前面有 1 个人比他高，名次 = 1 + 1 = 2
• 第 3 名：前面有 2 个人比他高，名次 = 2 + 1 = 3

所以只要数一数“班上有几个人的成绩比小明高”，再加 1，就是小明的名次。

来看样例： 5 个同学的成绩分别是 98、100、99、80、87，小明考了 98 分。

把每个成绩和小明比一比：

• 98：和小明一样高，不算比他高
• 100：比 98 大，比他高，cnt = 1
• 99：比 98 大，比他高，cnt = 2
• 80：比 98 小，不算
• 87：比 98 小，不算

比小明高的人数 cnt = 2，名次 = 2 + 1 = 3，和样例输出一致。

再举两个例子：

• 如果小明考了 100 分（全班最高），没有人比他高，名次 = 0 + 1 = 1，他就是第 1 名。
• 如果小明考了 50 分（全班最低），全班 3 个人都比他高，名次 = 3 + 1 = 4，他就排最后。

做法：先用数组把 n 个成绩存起来，再读入小明成绩 x， 然后循环遍历数组，数一数比 x 大的成绩有多少个，最后输出 cnt + 1。

参考代码

// P375 学员的名次
// 思路：把全班成绩存进数组，数一数有几个人比小明高，
//       名次 = 比小明成绩高的人数 + 1

#include <iostream>
using namespace std;

int main() {
    int n;        // 同学人数
    int a[105];   // 存全班成绩的数组
    int x;        // 小明的成绩
    int cnt = 0;  // 比小明分数高的人数

    // 第一步：读入同学人数 n
    cin >> n;

    // 第二步：读入 n 个成绩，存进数组 a
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 第三步：读入小明的成绩 x
    cin >> x;

    // 第四步：遍历数组，数一数有多少人比小明分数高
    for (int i = 0; i < n; i++) {
        if (a[i] > x) {
            cnt++;  // 每发现一个更高的，cnt 加 1
        }
    }

    // 第五步：名次 = 比小明高的人数 + 1
    cout << cnt + 1 << endl;

    return 0;
}

复杂度分析

• 时间复杂度：O(n)。程序把 n 个成绩读进数组花 O(n)，再从头到尾遍历数组比较一次又花 O(n)，加起来还是 O(n)。
• 空间复杂度：O(n)。我们用了一个长度为 n 的数组来存全班成绩。
• 题目保证 n <= 100，所以这个程序运行非常快，完全不会超时。