P4636 分数线划定（基础）

解题思路

这道题要找出「面试分数线」：先把选手按成绩从高到低排好，排名第 m×150%（向下取整）名的那位选手的成绩，就是分数线。它考察的是「排名」思想，而且利用了成绩范围小（1 到 100）的特点。

**第一步，读懂题意。**如果计划录取 m 名志愿者，就要按 150% 的比例多叫一些人来面试，所以要看排名第 m×150% 名的成绩。比如 m=3 时，3×1.5=4.5，向下取整就是第 4 名。

**第二步，算出身前名次。**m×150% 就是 m×3/2。用整数运算 planCount * 3 / 2，整数除法会自动向下取整：3×3/2 = 9/2 = 4，正好等于 4.5 向下取整的结果。

**第三步，用桶计数统计成绩。**成绩只有 1 到 100 共 100 种可能，所以我们可以开一个计数数组 scoreCount[101]，scoreCount[score] 表示考了 score 分的人数。读入每个成绩时，就在对应分数的桶里加 1。

**第四步，从高分往下找第 needRank 名。**从 100 分开始往下累加每个分数的人数，当累计人数第一次达到或超过 needRank 时，当前这个分数就是第 needRank 名所在的分数，也就是分数线。

**第五步，对照样例验证。**样例 6 个人成绩是 90、88、95、84、95、88：从 100 往下数，95 分有 2 人、90 分有 1 人，累计 3 人还不到 4 人；继续数到 88 分有 2 人，累计 5 人超过 4 人，所以第 4 名成绩是 88，分数线就是 88。

**第六步，确认边界。**题目保证 m×150% 向下取整后小于等于 n，所以第 needRank 名一定存在，不会出现数到底还不够人的情况。

参考代码

// 用成绩计数统计分数线，找出排名第floor(m*150%)名的成绩。
#include <iostream>
using namespace std;

int main() {
    int n; // 参加考试的人数。
    int planCount; // 计划录取人数。
    int scoreCount[101] = {0}; // scoreCount[score]表示成绩为score的人数。
    int i; // 循环变量。
    cin >> n >> planCount; // 读入人数和计划录取人数。
    for (i = 0; i < n; i++) { // 读入每个人的成绩。
        int score; // 当前考生的成绩。
        cin >> score; // 读入成绩。
        scoreCount[score]++; // 记录这个成绩出现了一次。
    }
    int needRank = planCount * 3 / 2; // 计划人数的150%，整数除法就是向下取整。
    int accumCount = 0; // 从高分开始累计的人数。
    int score; // 当前正在检查的成绩。
    for (score = 100; score >= 1; score--) { // 从最高分100向下检查。
        accumCount += scoreCount[score]; // 加上当前分数的人数。
        if (accumCount >= needRank) { // 找到排名第needRank名所在的分数。
            cout << score << '\n'; // 输出面试分数线。
            break; // 找到后结束循环。
        }
    }
    return 0; // 程序正常结束。
}

复杂度分析

时间上，读入 n 个成绩需要 O(n) 时间；从 100 分往下查找只需要最多 100 次循环，是常数时间 O(100)。所以总时间复杂度是 O(n)。空间上，只使用了一个大小固定的计数数组 scoreCount[101]，空间复杂度是 O(1)。n 最大为 5000，这个算法可以在极短时间内完成。相比先排序再取第 needRank 名的 O(n log n) 方法，利用成绩范围小这一特点的计数方法效率更高。