有n个数，共有2^n个子集，一个子集的值看做其所有数的和。
求这2^n个子集中第K大的子集。
n<=35。
首先我们可以通过meet in the middle的做法，将其分成两部分。
二分答案后用two point统计满足条件的方案总数。
与k进行比较即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define for(i,x,y) for(int i=x;i<=y;i++)
#define D "%d"
int n;int k,s,t=1,t2=1;
int a[1999],b[1999],c[1999],d[1999];
void dfs(int x,int ans){
if(x>=n/2+1) return ;
c[++t]=ans+a[x];
dfs(x+1,a[x]+ans);
dfs(x+1,ans);
}
void dfs2(int x,int ans){
if(x>=n+1) return ;
d[++t2]=ans+a[x];
dfs2(x+1,a[x]+ans);
dfs2(x+1,ans);
}
int check(int x)
{
int ans=0;int t3=t2;
for(i,1,t)
{
while(c[i]+d[t3]>=x&&t3>0)
t3--;
if(t3==0) break;
ans+=t3;
}
return ans;
}
int main()
{
scanf(D D,&n,&k);
for(i,1,n)
{
scanf(D,&a[i]);
s+=a[i];
}
c[1]=0;
d[1]=0;
dfs(1,0);
dfs2(n/2+1,0);
sort(c+1,c+t+1);
sort(d+1,d+t2+1);
/*for(i,1,t)
printf(D " ",c[i]);
printf("\n");
for(i,1,t2)
printf(D " ",d[i]);*/
int l=0,r=s+5;
while(l<=r)
{
int mid=(l+r)>>1;
int w=check(mid);
if(w>(1<<n)-k) r=mid-1;
else l=mid+1;
}
printf(D,r);
}