题记(27)--寻找大富翁

目录

一、题目内容

二、输入描述

三、输出描述

四、输入输出示例

五、完整C语言代码

一、题目内容

黑龙江ZD市共有n个人,请找出该镇上的前m个大富翁.

二、输入描述

每个用例首先包含2个整数n（0<n<=100000）和m(0<m<=10)，其中: n为镇上的人数，m为需要找出的大富翁数, 接下来一行输入镇上n个人的财富值.

三、输出描述

? 请输出前m个大富翁的财产数，财产多的排前面，如果大富翁不足m个，则全部输出,每组输出占一行.

四、输入输出示例

输入：

3 1
2 5 -1
5 3
1 2 3 4 5
0 0

输出：

5
5 4 3

考察nlogn的排序，暴力会超时。本文采用快排实现

五、完整C语言代码

AC代码~

#include<stdio.h>
#include<stdlib.h>
void QuickSort(int a[], int begin, int end) {
    int s = begin;
    int e = end;
    int key = a[begin];
    if (s < e) {
        while (s < e) {
            while (s < e && a[e] <= key)
                e--;
            while (s < e && a[s] >= key)
                s++;
            if (s < e) {
                int tmp = a[s];
                a[s] = a[e];
                a[e] = tmp;
            }
        }
        int tmp = a[e];
        a[e] = a[begin];
        a[begin] = tmp;
        key = e;
        QuickSort(a, begin, e - 1);
        QuickSort(a, e + 1, end);
    }
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0)
            break;
        int* a = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        QuickSort(a, 0, n - 1);
        if (m >= n) {
            for (int i = 0; i < n; i++)
                printf("%d ", a[i]);
            printf("\n");
        } else {
            for (int i = 0; i < m; i++)
                printf("%d ", a[i]);
            printf("\n");
        }
    }
    return 0;
}