这个题我先是打表找规律，发现他到最后的差分序列是先递减后递增，而且大部分都是前面的大，后面的小，但是有一部分是前面的小，后面的大。然后我就先按照前面说的，把初始序列构造出来，然后随机swap，swap玩了后再算答案，本来只是随便这样玩玩，发现<=50的大样例过了，然后交了一发，84pts 有没有大佬可以帮我解释一下，，，，，，， 有的时候，rand会带给我们惊喜

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
int a[10005];
int d[10005],d2[10005];
int b[10005];
int an[10005];
bool cmp(int a,int b){
	return a>b;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&a[i]),d[i]=a[i]-a[i-1];
	for(int i=1; i<=n; i++)b[i]=i;
	int ans=1000000000;
	if(n<=15){
		sort(d+2,d+1+n);
		do{
			for(int i=1; i<=n; i++)a[i]=a[i-1]+d[i];
			int now=0,sum=0,sum2=0;
			for(int i=1; i<=n; i++){
				sum+=a[i],sum2+=a[i]*a[i];
			}now=sum2*n-sum*sum;
			if(ans>=now){
				for(int i=1; i<=n; i++)an[i]=d[i];
			}
			ans=min(ans,now);
		}while(next_permutation(d+2,d+1+n));
		cout<<ans<<endl;
//		for(int i=1; i<=n; i++)cout<<an[i]<<" ";
//		cout<<endl;
	}else if(n<=400){
		sort(d+2,d+1+n,cmp);
		d2[1]=d[1];
		int l=2,r=n,cnt=2;
		int half=(n-1)/2;
		if((n-1)%2)half++;
		int ct=0;
		while(l<=r){
			d2[l]=d[cnt];
			cnt++;
			d2[r]=d[cnt];
			cnt++;
			ct++;
//			if(ct==half)swap(d2[l],d2[r]);
			l++,r--;
		}for(int i=1; i<=n; i++)a[i]=a[i-1]+d2[i];
		long long now=0,sum=0,sum2=0;
		for(int i=1; i<=n; i++){
			sum+=a[i],sum2+=a[i]*a[i];
		}now=sum2*n-sum*sum;
		long long ans=now;
		srand(time(NULL));
		for(int i=1; i<=1000000; i++){
			int l=rand()%n+2,r=n-l+2;
			swap(d2[l],d2[r]) ;
			for(int i=1; i<=n; i++)a[i]=a[i-1]+d2[i];
			long long now=0,sum=0,sum2=0;
			for(int i=1; i<=n; i++){
				sum+=a[i],sum2+=a[i]*a[i];
			}now=sum2*n-sum*sum;
			ans=min(ans,now);
		}
		cout<<ans;
	}else{
		sort(d+2,d+1+n,cmp);
		d2[1]=d[1];
		int l=2,r=n,cnt=2;
		int half=(n-1)/2;
		if((n-1)%2)half++;
		int ct=0;
		while(l<=r){
			d2[l]=d[cnt];
			cnt++;
			d2[r]=d[cnt];
			cnt++;
			ct++;
//			if(ct==half)swap(d2[l],d2[r]);
			l++,r--;
		}for(int i=1; i<=n; i++)a[i]=a[i-1]+d2[i];
		long long now=0,sum=0,sum2=0;
		for(int i=1; i<=n; i++){
			sum+=a[i],sum2+=a[i]*a[i];
		}now=sum2*n-sum*sum;
		long long ans=now;
		srand(time(NULL));
		for(int i=1; i<=10000; i++){
			int l=rand()%n+2,r=n-l+2;
			swap(d2[l],d2[r]) ;
			for(int i=1; i<=n; i++)a[i]=a[i-1]+d2[i];
			long long now=0,sum=0,sum2=0;
			for(int i=1; i<=n; i++){
				sum+=a[i],sum2+=a[i]*a[i];
			}now=sum2*n-sum*sum;
			ans=min(ans,now);
		}
		cout<<ans;
	}
	
	return 0;
}

码风很丑，，，，，不喜勿喷