Sum of Average 2AI (CI翻译)
Problem Statement
You are given a length-$N$ sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$.
Find the minimum possible value of $\displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor$ after rearranging $A$ in any order.
You are given $T$ test cases; solve each of them.
Constraints
$1\le T\le 10^5$$2\le N\le 2\times 10^5$$1\le A_i\le 10^9$- The sum of
$N$over all test cases is at most$2\times 10^5$. - All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_TEach test case is given in the following format:
N
A_1 A_2 \ldots A_NOutput
Output the answers for the test cases in order, separated by newlines.
{"titleZh":"平均值之和 2","bodyZh":"## 题目描述\n\n给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\\ldots,A_N)$。\n\n你可以按任意顺序重新排列 $A$。求 $\displaystyle \\sum_{i=1}^{N-1}\\left\\lfloor\\frac{A_i+A_{i+1}}2 \\right\\rfloor$ 的最小可能值。\n\n给定 $T$ 组测试用例，请分别求解。\n\n## 约束条件\n\n- $1\\le T\\le 10^5$\n- $2\\le N\\le 2\\times 10^5$\n- $1\\le A_i\\le 10^9$\n- 所有测试用例的 $N$ 之和不超过 $2\\times 10^5$。\n- 输入的所有数值均为整数。\n\n## 输入格式\n\n输入从标准输入按以下格式给出：\n\n\nT\n\\text{case}_1\n\\text{case}_2\n\\vdots\n\\text{case}_T\n`\n\n每组测试用例按以下格式给出：\n\n`\nN\nA_1 A_2 \\ldots A_N\n
样例
4
4
1 2 4 3
3
4 4 4
5
3 1 4 1 5
10
278117031 167642909 517897721 148434323 567739597 319926999 481642530 659199879 252516557 49913403
5
8
9
2829561210
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。