求助,为什么去掉这句就AC了
查看原帖
求助,为什么去掉这句就AC了
914358
Sicosuki楼主2023/10/17 13:38

为什么把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;
	}
}

我不觉得会影响答案啊

2023/10/17 13:38
加载中...