题目链接

题目大意

给定一个数列，你可以从中任取数字（不能不取）组成集合，可以得到很多集合。问：集合中所有数的和的第 k 小是多少？
不同但大小相同的数字组成的集合是不同的。例：1 1 可以组成 3 个集合 {1}, {1}, {1, 1}

解题思路

贪心，先从小到大排序，考虑加入集合。每次取下一个组合总是有两种取法：
1. 保持集合内个数不变，加入新的，删去旧的
1. 集合内个数+1，加入一个新的。
因此我们把这两种可能性都考虑到，把他们对应的值放入小根堆，每次堆顶的一定是最小，控制弹出堆顶k次即可。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int inf = 1e16;
const int N = 2e5 + 7;
int n,k;
struct node{
    int sum,id;
    friend bool operator < (node a,node b){
        if(a.sum == b.sum) return a.id > b.id;
        return a.sum > b.sum;
    }
};
int a[N];

priority_queue<node> q;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    q.push((node){a[1],1});
    node u;
    for(int i=1;i<=k;i++){
        u=q.top();
        //cout<<u.sum<<endl;
        q.pop();
        if(u.id+1<=n){
            q.push((node){u.sum+a[u.id+1]-a[u.id],u.id+1});
            q.push((node){u.sum+a[u.id+1],u.id+1});
        }
    }
    cout<<u.sum<<endl;
    return 0;
}