Lunar New Year and Number Division
题意翻译
【题目描述】
新年来了,Bob 正被他的家庭作业所为难,他需要完成一个划分数字的作业。
Bob 的作业上有 $n$ 个正整数 $a_1,a_2,{\dots},a_n$,其中 $n$ 为偶数,他要把这些数字进行分组,每组至少两个数字,假设分成了 $m$ 组,第 $j$ 组的数字之和是 $s_j$,Bob 需要最小化 $s_j$ 的平方和,即 $\sum^{m}_{j=1} s_j^2$。
Bob 被这题难住了,你可以帮帮他吗?
【输入格式】
第一行一个正偶数 $n$,表示 Bob 的作业上有 $n$ 个数。
接下来一行 $n$ 个整数,表示 Bob 作业上的数。
【输出格式】
输出一行表示 $s_j$ 的最小平方和,即$\sum^{m}_{j=1} s_j^2$,其中 $m$ 为数字组数。
【数据范围】
对于 $100\%$ 的数据,有 $2\leq n\leq 3\times 10^5, 1 \leq a_i \leq 10^4$。
题目描述
Lunar New Year is approaching, and Bob is struggling with his homework – a number division problem.
There are $ n $ positive integers $ a_1, a_2, \ldots, a_n $ on Bob's homework paper, where $ n $ is always an even number. Bob is asked to divide those numbers into groups, where each group must contain at least $ 2 $ numbers. Suppose the numbers are divided into $ m $ groups, and the sum of the numbers in the $ j $ -th group is $ s_j $ . Bob's aim is to minimize the sum of the square of $ s_j $ , that is $\sum_{j = 1}^{m} s_j^2. $
Bob is puzzled by this hard problem. Could you please help him solve it?
输入输出格式
输入格式
The first line contains an even integer $ n $ ( $ 2 \leq n \leq 3 \cdot 10^5 $ ), denoting that there are $ n $ integers on Bob's homework paper.
The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^4 $ ), describing the numbers you need to deal with.
输出格式
A single line containing one integer, denoting the minimum of the sum of the square of $ s_j $ , which is $ $$$\sum_{i = j}^{m} s_j^2, $ $ where $ m$$$ is the number of groups.
输入输出样例
输入样例 #1
4
8 5 2 3
输出样例 #1
164
输入样例 #2
6
1 1 1 2 2 2
输出样例 #2
27
说明
In the first sample, one of the optimal solutions is to divide those $ 4 $ numbers into $ 2 $ groups $ \{2, 8\}, \{5, 3\} $ . Thus the answer is $ (2 + 8)^2 + (5 + 3)^2 = 164 $ .
In the second sample, one of the optimal solutions is to divide those $ 6 $ numbers into $ 3 $ groups $ \{1, 2\}, \{1, 2\}, \{1, 2\} $ . Thus the answer is $ (1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27 $ .