题目描述:

中科附高计划派一支 m 人的队伍参加赛博空间挑战赛，已知中科附高共有学生 n 人，在该比赛所涉及内容的能力值分别为 a_{1}​, a_{2}​……a_{n} ​ ( 0 < a_{i} ​< k ) 。

由于是第一次参赛，带队的郝老师只能假设队伍的能力值为个人能力值之和。而且由于主场比赛想获得好成绩，郝老师计划派出能力值最强的队伍参赛，现在他想知道所派出的队伍的能力值是多少。

输入格式:

输入数据共两行。

第一行有三个自然数 n,m,k 。

第二行有 n 个自然数，分别是 a_{1}​, a_{2}​……a_{n} ​​。

输入数据以空格分隔，各变量含义如题面所述，其中 m \le n 。

输出格式:

输出一个整数，为所派队伍的能力值。输入数据保证该值不超过 2\times 10^9 。

输入样例:

5 2 4
2 3 1 0 3

输出样例:

6

数据范围:

测试点编号	n	m	k
0-2	\le10^3	\le n	\le 10^4
3-4	10^4	100	\le 10^5
5-6	\le 2 \times 10^7	\le 500	\le 3 \times 10^6
7-9	\le 5 \times 10^6	\le n	\le 10^9

思路:

题意是对序列内最大的 m 个数求和，但是使用数组+快排会MLE。所以考虑使用堆来动态维护数组内的前 m 大的数。C++要关闭流同步，不然读入数据就会TLE。

我的AC代码:

#include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

void solve(){
    uint n,m,k;
    cin >> n >> m >> k;
    priority_queue<uint,vector<uint>,greater<uint>> pq;
    for(int i = 0;i < n;i++){
        uint x;
        cin >> x;
        pq.push(x);
        if(pq.size() > m) pq.pop();
    }
    uint ans = 0;
    while(!pq.empty()){
        ans += pq.top();
        pq.pop();
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}