模拟退火[76,92]pts求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
const double MAX_TIME=0.95;
int n,a[N],c[N],cnt,cntans;
int rnd(int l,int r)
{
    return rand()%(r-l+1)+l;
}
double check()
{
    double p=0,cc=0;
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+c[i];
        p+=a[i];
    }
    p/=n;
    for(int i=1;i<=n;i++)
    {
        cc+=(a[i]-p)*(a[i]-p);
    }
    return cc/n;
}
bool cmp(int x,int y)
{
    return x>y;
}
double SA()
{
    double mn=1e18+7;
    while(true)
    {
        int _=rnd(n/3,n/3*2);
        sort(c+2,c+1+_,cmp);
        sort(c+1+_,c+1+n);
        double mk=check();
        for(double t=1e8;t>=1e-8;t*=0.9999)
        {
            int x=rnd(2,n),y=rnd(2,n);
            if(x==y)continue;
            swap(c[x],c[y]);
            double nk=check();
            if(nk<mk||(double)exp((mk-nk)/t)*RAND_MAX>rand())
            {
                mk=nk;
            }
            else
            {
                swap(c[x],c[y]);
            }
            mn=min(mn,mk);
            if((double)clock()/CLOCKS_PER_SEC>=MAX_TIME)
            {
                return mn*n*n;
            }
        }
    }
    return mn*n*n;
}
signed main()
{
    //freopen("variance4.in","r",stdin);
    srand(time(NULL));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        c[i]=a[i]-a[i-1];
    }
    cout<<(int)(SA()+0.99)<<"\n";
    return 0;
}