题解 AT3857 【Median Sum】
紫题
2018-10-23 11:02:23
01背包的思想+bitset优化
设$f[i][j]$为用前i个数,能否组成数字$j$ $(f[i][j]∈{0,1})$
转移:$f[i][j]=(f[i-1][j-a[i]])|(f[i-1][j])$
省去第一维,再用bitset进行整体的转移
再看中位数的选取
设所有数的总和为$sum$,如果$f[x]=1$,那一定有$f[s-x]=1$
所以$f[]$是对称的
直接从$sum/2$开始扫即可
```cpp
#include<iostream>
#include<bitset>
using namespace std;
int n,x,sum;
bitset<2000007>f;
int main(){
cin>>n;
f[0]=1;
for(int i=1;i<=n;i++){
cin>>x;
f|=f<<x;
sum+=x;
}
for(int i=(sum+1)/2;i<=sum;i++){
if(f[i]) {cout<<i<<endl;break;}
}
return 0;
}
```