洛谷 P3878 [TJOI2010]分金币 题解报告

#include
#define d 0.996//降温幅度 
#define lim 1e-10//停止温度
#define INF 1e9+7
using namespace std;
int n,t;
int a[35];
int ans=INF;
int del,now,nowx,nowy;
int calc()
{
	int sum1=0,sum2=0;
	for(int i=1;i<=n/2;i++) sum1+=a[i];//前一半金币的值
	for(int i=n/2+1;i<=n;i++) sum2+=a[i];//后一半金币的值
	return abs(sum1-sum2);//价值差 
}
void sa()
{
	double T=2021;//初始温度 
	while(T>lim)
	{
		nowx=rand()%n+1;//产生1~n内的两个随机种子 
		nowy=rand()%n+1;
		swap(a[nowx],a[nowy]);//交换两个金币的值 
		now=calc();
		del=now-ans;
		if(del<0) ans=now;//now比ans小，说明此时now更优 
		else if(exp(-del/T)<(double)rand()/RAND_MAX){//否则一定概率接受此解 
		}
		else swap(a[nowx],a[nowy]);//如果产生的now不如ans更优，需要把两个值再换回去，以此来稳定最优解 
		T*=d;
	}
}
void work()
{
	for(int i=1;i<=100;i++) sa();//多跑几次 
}
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int main()
{
	t=read();
	while(t--)
	{
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();//输入 
		ans=INF;//开始答案要赋极大值 
		work();
		printf("%d\n",ans);
	}
	return 0;
}