题意：
求子集和第k大，n,k<=1e6
思路：
优先队列经典题目，注意优先队列是默认按从大到小排的
代码：
#include#include#include#include#include#include#include#include#include#include#include#include #define fst first#define sc second#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))#define lson l,mid,root<<1#define rson mid+1,r,root<<1|1#define lc root<<1#define rc root<<1|1#define lowbit(x) ((x)&(-x)) using namespace std;typedef double db;typedef long double ldb;typedef long long ll;typedef unsigned long long ull;typedef pair PI;typedef pair PLL;const db eps = 1e-6;const int mod = 1e9+7;const int maxn = 4e5+100;const int maxm = 4e5+100;const int inf = 0x3f3f3f3f;const db pi = acos(-1.0);int n, k;ll a[maxn];priority_queue ,vector>, greater> >q;//priority_queue, vector >, greater > >q;int main(){ scanf("%d %d", &n, &k); for(int i = 1; i <= n; i++){ scanf("%lld", &a[i]); } sort(a+1,a+1+n); q.push({a[1],1}); int cnt = 0; while(cnt auto tmp = q.top(); q.pop(); ll ans = tmp.fst; int id = tmp.sc; if(id q.push({ans+a[id+1],id+1}); q.push({ans-a[id]+a[id+1], id+1}); } cnt++; if(cnt == k){ printf("%lld\n", ans); break; } } return 0;}
,vector
>, greater
> >q;//priority_queue
, vector
> >q;int main(){ scanf("%d %d", &n, &k); for(int i = 1; i <= n; i++){ scanf("%lld", &a[i]); } sort(a+1,a+1+n); q.push({a[1],1}); int cnt = 0; while(cnt auto tmp = q.top(); q.pop(); ll ans = tmp.fst; int id = tmp.sc; if(id q.push({ans+a[id+1],id+1}); q.push({ans-a[id]+a[id+1], id+1}); } cnt++; if(cnt == k){ printf("%lld\n", ans); break; } } return 0;}
京公网安备 11010802041100号