题目描述
现在有n枚金币，它们可能会有不同的价值，现在要把它们分成两部分，要求这两部分金币数目之差不超过1，问这样分成的两部分金币的价值之差最小是多少？
输入输出格式
输入格式：
每个输入文件中包含多组测试数据，输入文件的第一行是一个正整数T，用来说明文件中有多少组测试数据。接下来将依次给出所有测试数据的描述，每组测试数据的第一行是一个正整数n，表示共有n枚金币。第二行有n个正整数vi，分别给出每一枚金币的价值。
输出格式：
对每一组输入数据，输出一个非负整数，表示分成的两部分金币的价值差别的最小值。
输入输出样例
输入样例#1：
2
3
2 2 4
4
1 2 3 6
输出样例#1：
0
2
说明
对30%的数据，1 ≤ vi ≤ 1000
对100%的数据，1 ≤ n ≤ 30，1 ≤ vi ≤ 230，T ≤ 20
每个测试点时限1秒
注意：对于使用C/C++语言的选手，若需使用64位整型数，应声明为long long，若需使用scanf()/printf()/fscanf()/fprintf()等系列函数，应配合使用"%lld"标记符进行long long类型的输入输出。
看到这题的数据范围就满脑子想乱搞...
我感觉我的noip完了。
我可能也就只会这种乱搞题了，
就这样乱搞，实测可以AC。
但其实这个pi用都没有...
随便写都行
#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 = ;char ch=getchar();bool fu=;
while(!isdigit(ch)) {if(ch=='-')fu=;ch=getchar();}
while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();
return fu?-res:res;
} int T, n;
int a[];
int ans; inline int Calc()
{
int res1 = , res2 = ;
for (reg int i = ; i <= n ; i ++)
if (i <= (n + ) / ) res1 += a[i];
else res2 += a[i];
return abs(res1 - res2);
} inline void SA()
{
double T = 2333.0;
while(T > 1e-)
{
int x = rand() % ((n + ) / ) + , y = rand() % ((n + ) / ) + ((n + ) / );
if (x <= or x > n or y <= or y > n) continue;
swap(a[x], a[y]);
int newans = Calc();
int dert = ans - newans;
if (dert > ) 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 = ; i <= n ; i ++) a[i] = read();
ans = 1e9;
for (int i = ; i <= ; i ++) SA();
cout << ans << endl;
}
return ;
}