题目
题目：Lunar New Year and Number Division
题目大意：给定一个数字序列，可以任意分组（可调整顺序），但每组至少两个，求每组内数字和的平方的最小值
思路
首先，易证两两分组是最好的。
其次，我们假设将序列${a_i}$分成序列${b_i}$和${c_i}$,所以
$$sum=frac{1}{2}sum_{i=1}^{n}(b_i+c_i)^2$$
我们不关心这部分（因为不管怎么划分，这部分值都不会变）：
$$frac{1}{2}sum_{i=1}^{n}(b_i^2+c_i^2)$$
我们仅需考虑$sum_{i=1}^{n}b_ic_i$的最小值，由Rearrangement Inequality（排序原理）知，我们须将大者与小者两两结合。
时间复杂度：$mathcal{O}(n log n)$
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 typedef long long ll; 7 const int maxn = 300000 + 10; 8 int n,a[maxn]; 9 10 11 int main() 12 { 13 scanf("%d", &n); 14 for (int i = 0; i < n; i++) scanf("%d", &a[i]); 15 sort(a, a + n); 16 ll ans = 0; 17 for (int i = 0; i < n / 2; i++) 18 ans += (ll)1 * (a[i] + a[n - 1 - i]) * (a[i] + a[n - 1 - i]); 19 printf("%I64d ", ans); 20 return 0; 21 }