P4634 富豪排名（基础）

解题思路

这道题是经典的「结构体 + 排序」组合，要做的就是把 n 个富豪按财产从大到小排队，输出排名最靠前的 k 个。

**第一步，读懂题意。**每个富豪有两个信息：姓名（字符串）和财产（小数）。题目保证任意两个人的财产都不一样，所以排名不会出现并列；k 一定小于等于 n，答案一定存在。

**第二步，用结构体装信息。**就像做一张「富豪卡片」，卡片上同时写着姓名和财产。我们在代码里定义一个结构体 magnate，里面放一个 char name[25] 存姓名、一个 double property 存财产。n 个富豪就是 n 张卡片，放进数组 magnates 里。

**第三步，用 sort 按财产从大到小排序。**C++ 的 sort 默认是从小到大排，不符合题目要求，所以我们要自己写一个比较函数 cmp：它接收两个结构体，返回「第一个的财产是否比第二个大」。sort 每比较两个人，就会调用它来决定谁排前面，这样就能排出「财产大的在前」。

**第四步，输出前 k 名。**排序完成后，排名最靠前的 k 个人就在数组的最前面。循环输出前 k 个元素的名字和财产即可。

**第五步，注意输出格式。**名字和财产之间用一个空格分开，财产要保留两位小数，用 printf("%s %.2f") 最方便。比如样例里财产最多的是 Ffdixdmd，财产 272.47 亿，它就排第一。

**第六步，想想边界。**既然财产两两不同，就不存在「同分争议」；k 不超过 n，直接输出前 k 名不会越界。所以这道题只要把数据装进结构体、排好序、输出，就完成了。

参考代码

// 程序用途：按财产从大到小排序，输出财产排名前 k 位的富豪
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct magnate {
    char name[25];   // 姓名
    double property; // 财产（亿元）
};

bool cmp(const magnate &person1, const magnate &person2) {
    return person1.property > person2.property; // 按财产从大到小排序
}

int main() {
    int n, k;
    cin >> n >> k;
    struct magnate magnates[105]; // 保存所有富豪的信息
    for (int i = 0; i < n; i++) {
        cin >> magnates[i].name >> magnates[i].property; // 读入姓名和财产
    }
    sort(magnates, magnates + n, cmp); // 从大到小排序
    for (int i = 0; i < k; i++) {
        printf("%s %.2f\n", magnates[i].name, magnates[i].property); // 输出前k名，财产保留两位小数
    }
    return 0;
}

复杂度分析

时间上，排序是这道题的主要工作。C++ 的 sort 函数用的是快速排序，平均时间复杂度是 O(n log n)，在 n=100 时大约只需要几百次比较，非常快。读入和输出都是 O(n)。所以总时间复杂度是 O(n log n)。空间上，我们用一个大小为 n 的结构体数组保存所有富豪的信息，空间复杂度是 O(n)。n 最大只有 100，内存占用极小。