原题大意

qwb和李主席打算平分一堆宝藏，他们想确保分配公平，可惜他们都太懒了，你能帮助他们嘛？

输入包含多组测试数据，处理到文件结束。
每组测试数据的第一行是一个正整数N(0 <= N <=36 )表示物品的总个数。
接下来输入N个浮点数(最多精确到分)，表示每个物品的价值V（0<V<=1e9）。

对于每组测试数据，输出能够使qwb和李主席各自所得到的物品的总价值之差的最小值（精确到分），每组测试数据输出占一行。

算法分析

折半搜索+二分查找，注意可能会因为浮点数误差导致WA，解决方法是一开始*200化成LL，

程序代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 40;
ll N[maxn], a[maxn], b[maxn], sum1[1<<20], all_cost;
int n, na, nb;
int main() {
    while(~scanf("%d", &n)){
        na = nb = 0;
        all_cost = 0LL;
        for(int i = 1; i <= n; i++){
            double t;
            scanf("%lf", &t);
            N[i] = round(t*200);
            if(i < n/2){
                a[na++] = N[i];
            }
            else{
                b[nb++] = N[i];
            }
            all_cost+=N[i];
        }
        memset(sum1,0,sizeof(sum1));
        for(int i = 0; i <(1<<na); i++){
            ll sum = 0LL;
            for(int j = 0; j < na; j++){
                if(i & (1<<j)) sum += a[j];
            }
            sum1[i] = sum;
        }
        sort(sum1,sum1+(1<<na));
        ll ans = 1e18;
        for(int i = 0; i <= (1<<nb); i++){
            ll temp = 0LL;
            for(int j = 0; j < nb; j++){
                if(i & (1 << j)) temp+=b[j];
            }

            int pos = lower_bound(sum1,sum1+(1<<na),all_cost/2-temp)-sum1;
            ans = min(ans, abs((sum1[pos] + temp) - (all_cost-sum1[pos] - temp)));
        }
        printf("%.2lf\n", ans/200.0);
    }
    return 0;
}