MnZn模拟退火0pts求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=33;
const double MX=1e6;
int T,n;
double a[N][2],s[2];
double rnd(double l,double r)
{
    return (double)rand()/RAND_MAX*(r-l)+l;
}
signed main()
{
    srand(time(NULL));
    cin>>T;
    while(T--)
    {
        cin>>n;
        s[0]=s[1]=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            a[(i+1)/2][i%2]=x;
            s[i%2]+=x;
        }
        int ans=1e18+10;
        int s1=s[0],s2=s[1];
        for(int i=1;i<=40;i++)
        {
            for(double t=MX;t>=1e-4;t*=0.999)
            {
                int x=rnd(1,(n+1)/2+1),y=rnd(1,(n+1)/2+1);
                int c1=s1+a[y][1]-a[x][0],c2=s2+a[x][0]-a[y][1];
                //cout<<x<<" "<<y<<"\n";
                if(abs(s1-s2)>abs(c1-c2)||exp((double)((s1-s2)-(c1-c2))/t)>rnd(0,1))
                {
                    //cout<<t<<"\n";
                    s1=c1,s2=c2;
                    swap(a[x][0],a[y][1]);
                }
                ans=min(ans,abs(s1-s2));
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}