P4648 分数线（基础）

解题思路

选拔赛规定前 5 名获奖，但如果第 5 名的分数和后面的同学一样，这些同学就都算并列第 5 名，一起获奖。题目要求输出「分数线」（第 5 名同学所在的那个分数）和「获奖总人数」。

**第一步，读懂题意。**先按分数从高到低排序，分数最高的第 1 名、第 2 名……第 5 名获奖。如果第 5 名和后面的同学同分，这些同分同学也一起获奖，所以获奖人数可能超过 5 人。

**第二步，选择计数排序。**成绩都在 0 到 100 之间，范围小，所以用计数排序：scoreCount[score] 表示考 score 分的同学人数。先把所有分数计数，不用真的去排序。

**第三步，从高分往下找分数线。**从最高的 100 分开始往下累加人数，当累计人数第一次达到或超过 5 时，当前这个分数 score 就是分数线。因为我们是按从高到低的顺序数的，所以第 5 名同学正好被包含在这个分数里，并列的情况也一并处理了。

**第四步，统计获奖人数。**找到分数线后，再统计一遍所有分数大于等于分数线的同学人数，加起来就是获奖总人数。

**第五步，对照样例验证。**样例分数是 80 89 60 40 65 72 72 75 72 95：从 100 往下数，95（1人）、89（1人）、80（1人）、75（1人）累计到 4 人，再看到 72 分有 3 个人，累计到 7 人，达到 5 人，所以分数线是 72，获奖人数是 7 人，与样例一致。

**第六步，确认边界。**如果前 5 名分数各不相同，则正好 5 人获奖；如果第 5 名与后面并列，人数会超过 5，这是题目的特殊要求，我们的算法天然支持。

参考代码

// 统计成绩并确定第五名分数线和获奖人数
#include <iostream>
using namespace std;

int main() {
    int n; // 参赛人数
    cin >> n; // 读入参赛人数
    int scoreCount[101] = {0}; // scoreCount[score]表示分数score出现的次数
    for (int i = 0; i < n; i++) { // 依次读入每位同学的成绩
        int score; // 当前同学的成绩
        cin >> score; // 读入成绩
        scoreCount[score]++; // 记录这个成绩出现一次
    }
    int accumCount = 0; // 从高分开始累计的人数
    int scoreLine = 0; // 获奖分数线
    for (int score = 100; score >= 0; score--) { // 从最高分向最低分查看
        accumCount += scoreCount[score]; // 加上当前分数的同学人数
        if (accumCount >= 5) { // 已经包含第五名同学
            scoreLine = score; // 当前分数就是分数线
            break; // 找到分数线后停止查找
        }
    }
    int winnerCount = 0; // 获奖总人数
    for (int score = scoreLine; score <= 100; score++) { // 检查分数线及以上的分数
        winnerCount += scoreCount[score]; // 累加获奖人数
    }
    cout << scoreLine << ' ' << winnerCount << '\n'; // 输出分数线和获奖人数
    return 0; // 程序结束
}

复杂度分析

程序先循环 n 次读入并计数，再从 100 到 0 扫描一遍找分数线、又扫描一遍统计人数，总共两次扫描分数范围，时间复杂度是 O(n)。n 最大 50，非常快。空间上只用了长度 101 的计数数组，是 O(1) 常数空间。