Dreamoon and NightMarket Gym – 101234G(优先队列子集第K大)

题目链接

https://vjudge.net/problem/Gym-101234G

题目大意

给你n个数(2e5),问和第k(1e6)大的子集是多大?

解题思路

优先队列()

代码

#include <bits/stdc++.h>
const int maxn=212345;
using namespace std;
typedef pair<long long,int> P;
int n,k;
int a[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    priority_queue<P,vector<P>,greater<P> >q;
    q.push(make_pair(a[0],0));
    int id;
    long long ans=0;
    while(k--){
        ans=q.top().first;
        id=q.top().second;
        q.pop();
        if(id<n-1){
            q.push(make_pair(ans+a[id+1],id+1));
            q.push(make_pair(ans-a[id]+a[id+1],id+1));
        }
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注