Solution - Median Sum

其它题不是很写得动了跑来写一下这个题，还是挺有趣的。

给定由 \(n\) 个正整数 \(a_1, a_2, \dots, a_n\) 组成的可重集合，求出它的非空子集的和的中位数。

设 \(sum = \sum\limits_{i = 1} ^ n a_i\)。

首先是对于任意一个子集，设其和为 \(x\)，我们将其取反，就是选的改成不选，不选的改成选，那么前后子集之和是 \(sum\)，改之后的子集和就是 \(sum - x\)，不妨 \(x \leq sum - x\)，那么一定有 \(x \leq \dfrac{sum}{2}, sum - x \geq \dfrac{sum}{2}\)。如果这时候把空集也算进去（方便计算，而中位数取中间更大的那个即可，也就是从小到大排序之后位于 \(\dfrac{2 ^ n}{2} + 1 = 2 ^ {n - 1} + 1\) 位置的数），和 \(\leq \dfrac{sum}{2}\) 的子集个数就一定为 \(2 ^ {n - 1}\)。于是我们只需要找到第一个 \(> \dfrac{sum}{2}\) 的子集和就好了。

于是就转化成了一个存在性问题。因为这个 \(n, a_i \leq 2000\)，考虑直接设 \(f_{i, j}\) 表示前 \(i\) 个数的和能否是 \(j\)。转移不表，但是这样时空复杂度都是 \(O(n ^ 3)\) 的。滚动数组空间可以优化到 \(O(n ^ 2)\)，至于转移可以发现就是一堆或的操作，用 bitset 维护，为 \(O(\dfrac{n ^ 3}{w})\)，就可以过了。

namespace liuzimingc {
const int N = 2e3 + 5, M = 4e6 + 5;

int n, a[N], sum;
bitset<M> f[2];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
	f[0][0] = true;
	for (int i = 1; i <= n; i++) {
		f[i & 1] = f[i - 1 & 1]; // 不选第 i 个
		f[i & 1] |= f[i - 1 & 1] << a[i]; // 选第 i 个
	}
	for (int i = sum + 1 >> 1; ; i++) // >= sum / 2，隐含向上取整
		if (f[n & 1][i]) return cout << i << endl, 0;
	return 0;
}
} // namespace liuzimingc