正题

题目链接:https://www.luogu.com.cn/problem/AT3857

---

题目大意

给出 n n n个数字的一个序列 a a a，求它的所有非空子集的和的中位数。

1 ≤ n , a i ≤ 2000 1\leq n,a_i\leq 2000 1≤n,ai​≤2000

---

解题思路

考虑到假设所有数的和为 S S S，一个集合的和为 x x x，那么肯定有与其对应的另一个集合和为 S − x S-x S−x。

所以如果算空集的话中位数一定是 S 2 \frac{S}{2} 2S​，但是因为不算所以需要往后移一个，那就是和大于且最接近 S 2 \frac{S}{2} 2S​的一个集合。

考虑怎么求这个和，暴力背包显然会 T T T，但是因为我们只需要求能不能拼出这个数，所以直接用 b i t s e t bitset bitset就好了。

时间复杂度： O ( n 2 a i ω ) O(\frac{n^2a_i}{\omega}) O(ωn2ai​​)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int N=2010;
int n,sum,a[N];
bitset<N*N/2> f;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	int k=0;sum=(sum+1)/2;
	f[0]=1;
	for(int i=1;i<=n;i++)
		f=f|(f<<a[i]);
	while(!f[sum])sum++;
	printf("%d\n",sum);
	return 0;
}