题解：P3878 [TJOI2010] 分金币

· · 题解

背景

貌似写这篇文章时题解只有一篇是正确的。而这唯一的一篇做法又比较麻烦，所以给出了思路简单实现容易的正确做法。

题意

给你一个长度为 n 的序列，问选出 \left\lfloor \frac{n}{2}\right\rfloor 个数，选出的数之和与未选出的数之和的差的最小值。

思路

数据范围 n\le 30，如果直接状压显然不行，但是可以折半状压。

我们先考虑前一半的数字，状压考虑每个数选不选，统计出选和不选的数的数量差 cnt 和总和差 sum，用 set 记录前一半数字中，对于每种数量差可能的总和差。

然后考虑后一半的数字，同样算出选和不选的数量差 cnt' 与总和差 sum'，那么只要满足 cnt+cnt'=\left\lfloor \frac{n}{2}\right\rfloor 或 cnt+cnt'=\left\lceil \frac{n}{2}\right\rceil 即可，对 n 分奇偶讨论，可以得到 cnt' 对应的 cnt。而对于每个 cnt，最优的总和差一定是最接近 sum' 的上下两个数，二分即可。

这样做复杂度就是 O(T2^{\frac{n}{2}})，可以通过本题。

实现

#include<bits/stdc++.h>
using namespace std;
const int N = 40;
typedef long long LL;
int a[N],n;
set<LL> s[2 * N];
LL calc(LL x,LL y)
{
    auto t = s[x].lower_bound(y);
    if(t != s[x].end()) return (*t) - y;
    return 1e18;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int t;
    cin>>t;
    while(t --)
    {
        cin>>n;
        for(int i = 1; i <= n; i ++) cin>>a[i];
        for(int i = 0; i <= 2 * n; i ++) s[i].clear(),s[i].insert(1e18),s[i].insert(-1e18);
        LL res = 1e18,m = n / 2,k = n - n / 2;
        for(int i = 0; i < (1 << m); i ++)
        {
            LL cnt = n,sum = 0;
            for(int j = 1; j <= m; j ++)
                if((i >> j - 1) & 1) cnt ++,sum += a[j];
                else cnt --,sum -= a[j]; 
            s[cnt].insert(sum);
        }
        for(int i = 0; i < (1 << k); i ++)
        {
            LL cnt = n,sum = 0;
            for(int j = 1; j <= k; j ++)
                if((i >> j - 1) & 1) cnt --,sum -= a[m + j];
                else cnt ++,sum += a[m + j];
            if(n & 1)
            {
                if(cnt) res = min(res,(*s[cnt - 1].lower_bound(sum)) - sum);
                res = min(res,(*s[cnt + 1].lower_bound(sum)) - sum);
                if(cnt) res = min(res,sum - (*-- s[cnt - 1].upper_bound(sum)));
                res = min(res,sum - (*-- s[cnt + 1].upper_bound(sum)));
            }
            else
            {
                res = min(res,(*s[cnt].lower_bound(sum)) - sum);
                res = min(res,sum - (*-- s[cnt].upper_bound(sum)));
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}