P4663 录取分数线（基础）

解题思路

第一步，读懂题目。 N 个同学参加选拔，计划录取不超过 M 人。分数从高到低排好队之后，排在第 M 名同学的分数，就是录取分数线。比如四个分数 70、85、60、95，从高到低排成 95、85、70、60，当 M=2 时排名第 2 的分数是 85，分数线就是 85。

第二步，想想生活里的例子。 体育老师按跑得快的顺序排队，说"取前 M 名"，排在第 M 位的那个同学的成绩就是那条"线"。就算有同学分数并列，排在第 M 名位置上的分数依然作为分数线。

第三步，用归并排序从高到低排。 题目要求使用归并排序。归并排序的思路是"先拆成两半各自排好，再合并"：合并时每次取两半里较大的那个放进临时数组，最后拷回原数组，这样分治下去就能把整个数组排好。它比冒泡、选择排序都快，适合 N 很大的情况。

第四步，排完直接取答案。 排好后数组下标 0 是最高分，下标 M-1 就是第 M 名，直接输出 score[M-1] 即可。比如分数 70、85、60、95，归并排完后是 95、85、70、60，M=2 时输出下标 1 的数 85，和题意一致。

第五步，注意细节。 要保证 M 不超过 N。就算有同学分数并列，比如两个 85 分，排在第 M 名位置上的 85 依然作为分数线，我们只是取出第 M 名的分数，不需要管并列同学谁先谁后。另外 N 可能比较大（测试数据里接近二十万个分数），数组要开大一些，读入时用 std::ios::sync_with_stdio(false) 加快速度，避免超时。

参考代码

// P4663 录取分数线：归并排序把分数从高到低排好，第 M 个分数就是录取分数线
#include <iostream>
int score[2000005], temp[2000005];

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
        if (score[i] >= score[j]) temp[k++] = score[i++];
        else temp[k++] = score[j++];
    while (i <= mid) temp[k++] = score[i++];
    while (j <= r) temp[k++] = score[j++];
    for (int p = l; p <= r; p++) score[p] = temp[p];
}

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < n; i++) std::cin >> score[i];
    mergeSort(0, n - 1);   // 分数从高到低排序
    std::cout << score[m - 1] << "\n";   // 排名第 M 的分数就是录取分数线
    return 0;
}

复杂度分析

归并排序的时间复杂度是稳定的 O(N log N)，对 N 接近 20 万的数据也很快。递归归并需要额外的临时数组 temp，空间复杂度 O(N)。题目时间限制 1000ms，归并排序完全能胜任。因为只要取第 M 名，其实也可以不排完全部，但用归并排序一次排完再取，逻辑最简单，也符合题目"要求使用归并排序"的规定。