题解 CF1106C 【Lunar New Year and Number Division】
Anguei
2019-02-01 02:36:02
题目中保证 $N$ 是偶数，且要求每组分组都至少包含两个元素，这是一个相当大的提示：分出 $\frac{N}{2}$ 组数字，每组数字一最大一最小。
具体证明好像要用重排不等式，我不太会。翻译一下 jlf 老师的官方题解（翻译的可能不太好，见谅)：
> 这个题看起来很简单，证明也很简单。由于 $n$ 是偶数，所以最优分组策略是：最小的与最大的分一个组，第二小的与第二大的分一个组，以此类推。
> 首先，很容易证明这些数字的最佳分组时两两分组，所以证明是作为练习留给读者的。（大佬写证明怎么都这样 /(ㄒoㄒ)/~~
> 第二部分的证明是关于重排不等式的. 考虑排列 ${a_i}$. 假设有 ${b_i}$,${c_i}$ 且 $b_i=c_j$ 当且仅当 $b_j=c_i$. 那么它们的和 $$\frac{1}{2} \sum_{i=1}^{n}\left(b_{i}+c_{i}\right)^{2}$$ 就是 ${a_i}$ 的分组策略之一. 但我们关心的不是 $$\frac{1}{2} \sum_{i=1}^{n}\left(b_{i}^{2}+c_{i}^{2}\right)$$ 我们只想减小 $\sum_{i=1}^{n} b_{i} c_{i}$. 这就直接应用了重排不等式。
> **时间复杂度**: $\mathcal{O}(n \log n)$
```cpp
#define int long long
const int N = 300000 + 5;
int n, s = 0, a[N];
int sqr(int x) { return x * x; }
void solution() {
n = read(); rep(i, 1, n) a[i] = read();
std::sort(a + 1, a + n + 1);
rep(i, 1, n >> 1) s += sqr(a[i] + a[n + 1 - i]);
println(s);
}
```