【51nod 3046】子集和的元素和（DFS）（二分）

题目大意

给出长度为 n n n 的集合 A A A ， A A A 的非空子集合共有 2 n − 1 2^n-1 2n−1 个，每个子集合有一个元素的加和 S u m Sum Sum 。求所有 S u m Sum Sum 中第 K K K 小的 S u m Sum Sum 。

输入格式

第一行： 2 2 2 个数 n , k n,k n,k 。（ 1 ≤ n ≤ 50000 , 1 ≤ k ≤ 200000 1\le n\le 50000, 1\le k\le 200000 1≤n≤50000,1≤k≤200000 ） 第 2 ∼ n + 1 2 \sim n+1 2∼n+1 行：每行一个数 A i Ai Ai 。（ 1 ≤ A i ≤ 1 0 9 1\le Ai\le 10^9 1≤Ai≤109 ）

输出格式

输出一个数，对应第 K K K 小的 S u m Sum Sum 。

输入样例

3 5
1
2
3

输出样例

4

数据范围

对于 16 16% 16 的数据， 1 ≤ n ≤ 20 , 1 ≤ k ≤ 100 1\le n\le 20, 1\le k\le 100 1≤n≤20,1≤k≤100 ， 1 ≤ A i ≤ 50 1\le Ai\le 50 1≤Ai≤50 ；

对于 60 60% 60 的数据， 1 ≤ n ≤ 2000 , 1 ≤ k ≤ 10000 1\le n\le 2000, 1\le k\le 10000 1≤n≤2000,1≤k≤10000 ， 1 ≤ A i ≤ 2 × 1 0 6 1\le Ai\le 2\times 10^6 1≤Ai≤2×106 ；

对于 100 100% 100 的数据， 1 ≤ n ≤ 50000 , 1 ≤ k ≤ 200000 1\le n\le 50000, 1\le k\le 200000 1≤n≤50000,1≤k≤200000 ， 1 ≤ A i ≤ 1 0 9 1\le Ai\le 10^9 1≤Ai≤109 ；

样例解释

1 , 2 , 3 1,2,3 1,2,3 的非空子集合包括： ( 1 ) , ( 2 ) , ( 3 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) , ( 1 , 2 , 3 ) (1),(2),(3),(1,2),(1,3),(2,3),(1,2,3) (1),(2),(3),(1,2),(1,3),(2,3),(1,2,3) 。对应元素和为： 1 1 1 ， 2 2 2 ， 3 3 3 ， 3 3 3 ， 4 4 4 ， 5 5 5 ， 6 6 6 。其中第 5 5 5 小的为 4 4 4 。

基本思路

我们看到 n n n 的范围有 50000 50000 50000 ，所以 A A A 的非空集合数量是 2 50000 − 1 2^{50000} - 1 250000−1 ，这是绝对不可能完全枚举的。

这种情况下如何求第 k k k 大的呢？这需要我们转换思路，从求第 (k) 大转换为猜第 k k k 大的是多少？

k k k 越小对应的结果越大， k k k 越大对应的结果越小，因此 k k k 同结果直接具有单调性，我们用二分来猜测最终的结果，用 D F S DFS DFS 来验证结果的数量。

即二分最终的答案，然后利用 D F S DFS DFS 统计有多少组解小于这个答案，但需要注意的是， D F S DFS DFS 时当解的数量达到了 K K K 个就要退出（边界条件），否则复杂度无法保证。

这样时间复杂度为 O ( n + k ( l o g ( s u m ) ) ) O(n+k(log(sum))) O(n+k(log(sum))) ，其中 s u m sum sum 为所有数字的和。

但实际提交时我们会发现它还是会超时，我尝试对原数组排序来优化它的速度，最后发现对原数组降序排序之后，程序运行堪称神速，这个我没有仔细去验证，但这个是个必要的优化。

核心代码

#includeusing namespace std;
typedef unsigned long long ull;
const int N=5e4+10;
ull n,k,a[N],cnt,l,r,mid;
inline void dfs(ull p,ull sum,const ull num){if(sum>=num) return;
	if(cnt>k) return;//这一步至关重要
	cnt++;
	for(register ull i=p;i<=n;i++){if(sum+a[i]k) return;
	}
}
inline bool check(ull x){cnt=0;
	dfs(1,0,x);
	if(cnt>k) return false;
	return true;
}
bool cmp(ull x,ull y){return x>y;
}
int main(){ios::sync_with_stdio(false);
	cin>>n>>k;
	for(register int i=1;i<=n;i++){cin>>a[i];
		r+=a[i];
	}
	sort(a+1,a+1+n,cmp);
	l=a[n];
	while(lmid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<