题干：

小a非常喜欢204204这个数字，因为′a′+′k′=204′a′+′k′=204。
现在他有一个长度为nn的序列，其中只含有2,0,42,0,4这三种数字
设aiai为序列中第ii个数，你需要重新排列这个数列，使得∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0a0=0

输入描述:

第一行一个整数nn
接下来一行nn个整数，第ii个数表示aiai

输出描述:

输出一个整数，表示∑ni=1(ai−ai−1)2∑i=1n(ai−ai−1)2的最大值

示例1

输入

复制

2
2 4

输出

复制

20

说明

样例1解释：按(4,2)(4,2)排列是最优的，此时sum=(4−0)2+(2−4)2=20sum=(4−0)2+(2−4)2=20

示例2

输入

复制

3
2 0 4

输出

复制

36

说明

样例2解释：按(4,0,2)(4,0,2)排列是最优的，此时sum=(4−0)2+(0−4)2+(2−0)2=36sum=(4−0)2+(0−4)2+(2−0)2=36

示例3

输入

复制

5 
2 4 0 2 4

输出

复制

52

备注:

1⩽n⩽1051⩽n⩽105，保证aiai为2/0/42/0/4中的数

解题报告：

   直接构造就可以了，，写的不好会使得代码丑陋233、、这样贪心的正确性证明不太好说，，（有种情况，，比如2多出来很多，那么最后会是连续的2 2 2 2 2 2，所以没有贡献，会不会把2插入序列中，使得结果优于4 0 4 0 2 2 2 2 2这样？）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
int a[MAX],b[MAX];
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
	sort(a+1,a+n+1);
	for(int i = 1,l=1,r=n; i<=n; i++) {
		if(i%2==1) b[i] = a[r],r--;
		else b[i] = a[l],l++;
	}
	ll ans = 0 ;
	for(int i = 1; i<=n; i++) ans += (b[i] - b[i-1])*(b[i] - b[i-1]);
	printf("%lld\n",ans);

	return 0 ;
 }