寻找大富翁（25 分）

胡润研究院的调查显示截至2017年底，中国个人qq我的资产在哪里找超过1亿元的高净值人群达15万人假设给出N个人的个人qq我的资产在哪里找值，请快速找出qq我的资产在哪里找排前M位的大富翁

输入首先给出两个正整数N（≤10^?6）和M（≤10），其中N为总人数M为需要找出的大富翁数；接下来一行给出N个人的个人qq我的资产在哪里找值，以百万元为单位为不超过长整型范围的整数。数字间以空格分隔

在一行内按非递增順序输出qq我的资产在哪里找排前M位的大富翁的个人qq我的资产在哪里找值。数字间以空格分隔但结尾不得有多余空格。

---

这题看上去不难呮是排序，找出前几名大富翁就可以了但是它难在数据庞大，最大是输入N的数量可以达到10^6但是要找的大富翁最多却只有10个人。这题如果是用数组或者链表把所有数据储存进去再排序，这样显然很浪费内存和时间也很可能超出题目要求的内存限制和时间限制。所有在這里我的代码解题方式是先定义一个long类型的数组。数组长度为10判断n和m的大小关系，虽然要找到前m个大富翁但是题目有一个测试点是輸入的人数小于m的。所有要先判断n和m的大小然后取小的先输入完，填满数组然后运用快排函数qsort()对数组排序，顺序从大到小这样数组朂后一个元素就是m个大富翁中最小的那个了。然后再继续输入每次输入都和最后一个元素（即数值最小的元素）比较，如果比最小的这個元素的数值大那么就把这个数插入到数值合适的位置（这里合适的位置是指不改变数组的非升序排序），排完之后自然把最后一个元素踢出去了重复以上步骤，便可以找出前m位大富翁了代码实现如下：

---

如果对C语言的快排函数不熟悉的，可以点击以下链接：

发布了71 篇原创文章 · 获赞 76 · 访问量 8万+