P4646 兔子排行榜（提高）

解题思路

兔子王国有 n 名考生，要按总成绩从高到低排出前 k 名。麻烦的地方在于：如果两只兔子成绩相同，必须按照输入的先后顺序输出（先输入的排前面），也就是要「稳定」排序。所以这一题用归并排序，并且在比较时如果成绩相同就比较输入顺序编号。

**第一步，读懂题意。**读入 n 和 k，再读入 n 只兔子的姓名和成绩，按成绩从高到低输出前 k 名。成绩相同时，输入顺序靠前的排前面。

**第二步，理解稳定排序的必要性。**普通排序遇到成绩相同的兔子时，先后顺序不保证，这不符合题目要求。所以我们要在比较规则里加一个条件：成绩相同的时候，比较输入顺序编号 order，编号小的先输出，这样就能保证「同分先输入的排前面」。

**第三步，理解归并排序的思路。**归并排序是「先拆后合」：先把整个数组从中间一分为二，左半边和右半边各自排好序，再把两个有序的数列合并成一个。合并时两个指针分别指向左右两半的开头，谁的成绩高谁就先进入暂存数组；如果成绩相同，输入顺序编号小的先进。

**第四步，用结构体装信息。**定义一个结构体 Rabbit，里面保存兔子的姓名（字符数组 name）、总成绩（score）和输入顺序编号（order）。n 最大是 100000，归并排序的时间是 O(n log n)，可以轻松通过。注意姓名要用定长字符数组保存，因为题目要求不能用 string。

**第五步，确认边界。**k 比 n 小，但可以很接近 n，所以数组要开到 100000；排序完成后只需要输出前 k 行，每行是姓名和成绩，中间用空格隔开。成绩相同这一「并列名次」的场景，一定要用 order 比较来保证稳定。

参考代码

// 使用稳定归并排序按成绩降序整理兔子排行榜
#include <iostream>
using namespace std;

struct Rabbit {
    char name[101]; // 兔子姓名
    int score;      // 兔子总成绩
    int order;      // 兔子的输入顺序
};

Rabbit rabbits[100000]; // 保存所有兔子
Rabbit temp[100000];    // 归并时暂存兔子

void mergeSort(int left, int right) {
    if (left >= right) { // 只有一个元素时已经有序
        return; // 结束本次递归
    }
    int mid = (left + right) / 2; // 把区间分成左右两半
    mergeSort(left, mid); // 排序左半部分
    mergeSort(mid + 1, right); // 排序右半部分
    int i = left; // 左半部分当前位置
    int j = mid + 1; // 右半部分当前位置
    int k = left; // 暂存数组写入位置
    while (i <= mid && j <= right) { // 两边都还有元素时比较
        if (rabbits[i].score > rabbits[j].score || (rabbits[i].score == rabbits[j].score && rabbits[i].order < rabbits[j].order)) { // 成绩高或同分且输入更早
            temp[k] = rabbits[i]; // 先放入左边兔子
            i++; // 左边位置向后移动
        } else { // 右边兔子应该先放入
            temp[k] = rabbits[j]; // 放入右边兔子
            j++; // 右边位置向后移动
        }
        k++; // 暂存数组位置向后移动
    }
    while (i <= mid) { // 左边还有剩余兔子
        temp[k] = rabbits[i]; // 放入左边剩余兔子
        i++; // 左边位置向后移动
        k++; // 暂存位置向后移动
    }
    while (j <= right) { // 右边还有剩余兔子
        temp[k] = rabbits[j]; // 放入右边剩余兔子
        j++; // 右边位置向后移动
        k++; // 暂存位置向后移动
    }
    for (int pos = left; pos <= right; pos++) { // 把暂存结果复制回原数组
        rabbits[pos] = temp[pos]; // 覆盖当前区间
    }
}

int main() {
    int n; // 兔子总数
    int k; // 需要输出的前几名
    cin >> n >> k; // 读入兔子总数和名次数量
    for (int i = 0; i < n; i++) { // 依次读入所有兔子
        cin >> rabbits[i].name >> rabbits[i].score; // 读入姓名和成绩
        rabbits[i].order = i; // 保存输入顺序
    }
    mergeSort(0, n - 1); // 按规则进行稳定排序
    for (int i = 0; i < k; i++) { // 只输出前k名
        cout << rabbits[i].name << ' ' << rabbits[i].score << '\n'; // 输出姓名和成绩
    }
    return 0; // 程序结束
}

复杂度分析

归并排序每一层要合并所有 n 个元素，一共约 log n 层，所以时间复杂度是 O(n log n)。当 n=100000 时，大约要比较 100000×17 次，运行速度很快。程序用了两个结构体数组 rabbits 和 temp 各存 n 只兔子，空间复杂度是 O(n)。