NEFU-1650 没必要的排序2

NEFU-1650 没必要的排序2

/ 0评 / 1476次 / 0

Description

羽裳有n个数,她想知道前k大的数的和是多少

Input

输入n,k代表有n个数,求前k大的和,之后输入n个数,第i个数为a[i]1<=n<=10000000(1e7)1<=k<1000对任意的i1<=a[i]<=100000(1e5)

Output

输出一个数ans,ans是前k大数的和

Accepted Code

#include <bits/stdc++.h>
using namespace std;
int maxm[100005];
int main()
{
    memset(maxm, 0, sizeof(maxm));
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        maxm[tmp]++;
    }
    for (int i = 100000; i >= 1; --i)
    {
        while (maxm[i]-- && k > 0)
        {
            --k;
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}

解后反思

桶排序即可

发表回复

您的电子邮箱地址不会被公开。

你好 No.59613