#C241024E. [TJOI2010] 分金币

标签（Label）

模拟退火
模板

网址（Website）

P3878 [TJOI2010] 分金币 - 洛谷

题解（Solution）

$\qquad$ 直接模退就好啦~

$\qquad$注意初始温度设置在 $\verb!(1e-15,1e5)!$ 比较好，当然是在每一次验证都比较小的情况下，降温参数喜欢用 $\verb!0.9995!$ ，既不会超时，也保证了随机次数，然后就直接跳就可以了。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;
int T,tt;double Tim;mt19937_64 rr(time(0));
inline int rnd(int l,int r){return rr()%(r-l+1)+l;}
inline double rndd(double l,double r){return rnd(1,1e12)/1e12*(r-l)+l;}

int n,ans,a[N];

int calc(){
	int r1=0,r2=0;For(i,1,n/2) r1+=a[i];For(i,n/2+1,n) r2+=a[i];
	return ans=min(ans, abs(r1-r2)),abs(r1-r2);
}

void SA(){
	int cur = calc();
	for(double T = 1e5;T>=1e-15;T*=0.9995){
		int l = rnd(1,n), r = rnd(1,n);
		if(l>r) swap(l,r);swap(a[l],a[r]);
		int now = calc(), delta = now - cur;
		if(exp(-delta/T)>rndd(0,1)) cur = now;
		else swap(a[l],a[r]);
	}
}

void Solve(){
	Tim = clock();
	ans = inf, n = rd();For(i,1,n) a[i] = rd();
	while((clock()-Tim)/CLOCKS_PER_SEC*tt<0.9) SA();
	printf("%lld\n", ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	T  = tt = rd();while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}