题解 P3878 【[TJOI2010]分金币】

Yeji_ · 2019-05-21 12:30:03 · 题解

分金币

前言

模拟退火，好东西。

思路

历程

这道题一看就感觉是暴力枚举啊！！！

但是不出人意料的，过不了。

所以开始思考正解，所以开始了漫长的思考时间。

one hour......

two hour......

a long long time......

想不出来怎么办啊？？？？

还是看题解吧！！！

正解

折半状压？这是什么，赶紧脑补一波

按个数为第一关键字，权值为第二关键字对刚刚记录的方案排序，

这样对于选的数个数相同的方案就会被放在一起形成一个个有序的区间，

同时记录每个区间的左端点。 ——取自 star_city

我怎么没有想到！！！

但是，本篇详解的是模拟退火

水分神器——模拟退火

因为本题是要求平分，所以我们先锁边乱搞一下，分成两个组别，

每次在把一个组和另一个组的金币交换

显然，这一个过程可以用模拟退火来实现

一定是随机的，如果不会模拟退火，那么日报里也有大佬讲的模拟退火非常详细，值得一看。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define inf 2147483647
#define re register
using namespace std;
int n,ans=inf,a[1005];
int get()
{
    int sum1=0,sum2=0;
    for (re int i=1;i<=(n+1)/2;i++)
        sum1+=a[i];
    for (re int i=(n+1)/2+1;i<=n;i++)
        sum2+=a[i];
    return abs(sum1-sum2);
}
void SA()
{
    double beginT=5000,endT=1e-10,changeT=0.9112;
    for (re double T=beginT;T>endT;T*=changeT)
    {
        int x=rand()%n+1, y=rand()%n+1;
        swap(a[x],a[y]);
        int sum=get();
        if (sum<ans)
             ans=sum;
        else 
            if (exp((ans-sum)/T)<(double(rand())/RAND_MAX))
                swap(a[x],a[y]);
    }
}
int main()
{
    srand(rand());
    int T;
    cin>>T;
    while (T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int ctrl=1000;
        while(ctrl--)
            SA();
        cout<<ans<<endl;
        ans=inf;
    }
}