题目描述
现在有n枚金币,它们可能会有不同的价值,现在要把它们分成两部分,要求这两部分金币数目之差不超过1,问这样分成的两部分金币的价值之差最小是多少?
输入格式
每个输入文件中包含多组测试数据,输入文件的第一行是一个正整数T,用来说明文件中有多少组测试数据。接下来将依次给出所有测试数据的描述,每组测试数据的第一行是一个正整数n,表示共有n枚金币。第二行有n个正整数vi,分别给出每一枚金币的价值。
输出格式
对每一组输入数据,输出一个非负整数,表示分成的两部分金币的价值差别的最小值。
模拟退火模板题,讲解在代码中
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define int long long
using namespace std;
int t,n,ans;
int v[50];
inline 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*10+ch-'0';ch=getchar();}
return x*f;
}
int sums(){
int sum1=0,sum2=0;
for(int i=1;i<=(n+1)/2;i++) sum1+=v[i];
for(int i=(n+1)/2+1;i<=n;i++) sum2+=v[i];
return abs(sum1-sum2);
}
void SA(){
double b=5000.00,e=1e-10;
double ch=0.9223;
for(double i=b;i>e;i=i*ch){
int x=rand()%n+1;
int y=rand()%n+1;
swap(v[x],v[y]);
int lgr=sums();
if(lgr<ans) ans=lgr;//如果是当前最优值则更新
else if(exp((ans-lgr)/i)<(double(rand())/RAND_MAX))swap(v[x],v[y]);//如果不是当前最优值以一定概率更新,这是公式。
}
}
main(){
t=read();
while(t--){
ans=2147483647;
n=read();
for(int i=1;i<=n;i++) v[i]=read();
for(int i=1;i<=1000;i++) SA();//我脸好黑啊,1000遍才能过,草
printf("%lld\n",ans);
}
return 0;
}