为什么把sa()里面的
ans = get()
去掉就AC了
#include <iostream>
#include <algorithm>
#include <cmath>
#include <random>
#define int long long
using namespace std;
const int ma = 50,inf = 99999999999999;
const double det = 0.997;
const int MAX = 4294967295;
int T,n,a[ma],ans = inf,mid;
int get()
{
int lsum=0,rsum=0;
for(int i = 1; i <= mid; i++)
lsum += a[i];
for(int i = mid+1; i <= n; i++)
rsum += a[i];
return abs(lsum-rsum);
}
void sa()
{
double t = 3000;
mt19937 ra(random_device{}());
shuffle(a+1,a+n+1,ra);
//ans = get() 加上这句就爆零或10分,去掉就AC
while(t > 1e-10)
{
int l = ra() % n+1;
int r = ra() % n+1;
swap(a[l],a[r]);
int nw = get();
double dt = nw - ans;
if(dt < 0)
ans = nw;
else if(exp(-dt/t)*MAX < (double)ra())
swap(a[l],a[r]);
t *= det;
}
}
signed main()
{
cin >> T;
for(int i = 1; i <= T; i++)
{
ans = inf;
cin >> n;
mid = n/2 + (n%2);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int j = 1; j <= 100; j++)
sa();
cout << ans << endl;
}
}
我不觉得会影响答案啊