算法
(bitset优化01背包) $O(\frac{NS}{64})$
题意:
给定 $n$ 个正整数 $a_1,a_2,\cdots, a_n$,这些正整数可以组成 $2^{n}-1$个集合(不算空集)。注意,这里的集合允许有相同的元素。分别计算这些集合的元素之和,请你从这些集合的和中,找到它们的中位数(排序后名次恰好在中间的数字)。
例如对于 $2,3,3$ 来说,可以组成的子集有
$$\{2\},\{3\},\{3\},\{2,3\},\{2,3\},\{3,3\},\{2,3,3\}$$
分析:
记原序列的总和为 $S$
容易发现如果把空集也考虑进去的话,在左边任取一个子集,其和为 $x$,那么一定可以在右边找到一个子集满足它的和为 $S - x$。也就是说,位于权值为 $\frac{S}{2}$ 的左右两边的子集是对称的。
于是,我们就能推出我们需要求的中位数就是总和超过 $\frac{S}{2}$ 的第一个子集,但直接做 01
背包的话复杂度会炸
这时候有个奇技淫巧,叫 bitset
。它的主要作用就是能使几万位的二进制数实现 $O(\frac{n}{w})$ ($w$ 表示计算机的位数) 复杂度的位运算。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::bitset;
const int MX = 2005;
const int M = MX*MX;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int s = 0;
rep(i, n) s += a[i];
bitset<M> dp;
dp[0] = 1;
rep(i, n) dp |= dp<<a[i];
for (int i = (s+1)/2; i < M; ++i) {
if (dp[i]) {
cout << i << '\n';
return 0;
}
}
return 0;
}