luogu P3878 [TJOI2010]分金币

[返回模拟退火略解]

题目描述

今有 nnn 个数 {ai}\{a_i\}{ai​}，把它们分成两堆{X},{Y}\{X\},\{Y\}{X},{Y}，求一种分配使得∣∑i∈Xai−∑i∈Yai∣|\sum_{i\in X}{a_i}-\sum_{i\in Y}{a_i}|∣i∈X∑​ai​−i∈Y∑​ai​∣的值最小。

Solution 3878\text{Solution 3878}Solution 3878 解法一

模拟退火SA。

尝试重新排列 aaa，将 aaa 的前半部分分成一堆，后半部分分成一堆，求出解。

贴上 BriMon dalao的代码。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <ctime>

#include <cmath>

using namespace std;

#define reg register

inline int read() {

    int res = 0;char ch=getchar();bool fu=0;

    while(!isdigit(ch)) {if(ch=='-')fu=1;ch=getchar();}

    while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48), ch=getchar();

    return fu?-res:res;

}

int T, n;

int a[35];

int ans;

inline int Calc()

{

    int res1 = 0, res2 = 0;

    for (reg int i = 1 ; i <= n ; i ++)

        if (i <= (n + 1) / 2) res1 += a[i];

        else res2 += a[i];

    return abs(res1 - res2);

}

inline void SA()

{

    double T = 2333.0;

    while(T > 1e-9)

    {

        int x = rand() % ((n + 1) / 2) + 1, y = rand() % ((n + 1) / 2) + ((n + 1) / 2);

        if (x <= 0 or x > n or y <= 0 or y > n) continue;

        swap(a[x], a[y]);

        int newans = Calc();

        int dert = ans - newans;

        if (dert > 0) ans = newans;

        else if (exp((double)((double)dert/T)) * RAND_MAX <= rand()) swap(a[x], a[y]);

        T *= 0.998;

    }

}

int main()

{

    T = read();

    srand((unsigned)time(NULL));

    while(T--)

    {

        n = read();

        for (reg int i = 1 ; i <= n ; i ++) a[i] = read();

        ans = 1e9;

        for (int i = 1 ; i <= 50 ; i ++) SA();

        cout << ans << endl;

    }

    return 0;

}

Solution 3878\text{Solution 3878}Solution 3878 解法二

尝试 dfs 剪枝。

每个金币有取和不取 222 种状态，最多 303030 个金币，深搜需 2302^{30}230 的时间。然而可以优化。

按价值从大到小排序，你一不小心取的价值太大会被剪枝。

最多取 n2\frac{n}{2}2n​ 个金币，你取得太多是要被剪枝的。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define reg register

typedef long long ll;

int T,n;

ll a[40],s,ans;

bool b[40];

int hh[40];

int cmp(int a,int b){

	return a>b;

}

ll h(int x,int y){

	return hh[y]-hh[x-1];

}

ll dfs(int c,int x,ll X,int y,ll Y)

{

    if(x>n/2||y>n/2) return ans;

    ll nx=X+h(c,c+(n/2-x)-1);

    if(nx<=s-nx) return(s-nx-nx);

    nx=X+h(n-(n/2-x)+1,n);

    if(nx>=s-nx) return(nx-(s-nx));

    ll p=dfs(c+1,x+1,X+a[c],y,Y);

    ll q=dfs(c+1,x,X,y+1,Y+a[c]);

    if(p<q) return p;

	return q;

}

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		s=0;ans=1e17;

		for(reg int i=1;i<=n;++i){

			scanf("%lld",&a[i]);

			s+=a[i];

		}

		if(n%2){

			++n;

			a[n]=0;

		}

		std::sort(a+1,a+n+1,cmp);

		for(reg int i=1;i<=n;++i)

			hh[i]=hh[i-1]+a[i];

		printf("%lld\n",dfs(1,0,0,0,0));

	}

}