C - Sum of Average 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

A を好きな順序に並べ替えた後の \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor としてあり得る最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 10^5
  • 2\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • 全てのテストケースにおける N の総和は 2\times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
A_1 A_2 \ldots A_N

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

入力例 1

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

出力例 1

5
8
9
2829561210

1 番目のテストケースについて考えます。

たとえば A=(3,2,1,4) に並べ替えることで \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor=\left\lfloor\frac52\right\rfloor+\left\lfloor\frac32\right\rfloor+\left\lfloor\frac52\right\rfloor=5 となります。

どのように並べ替えても \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor の値は 5 以上となるため、答えは 5 になります。

Score : 500 points

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}_T

Each test case is given in the following format:

N
A_1 A_2 \ldots A_N

Output

Output the answers for the test cases in order, separated by newlines.

Sample Input 1

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

Sample Output 1

5
8
9
2829561210

Consider the first test case.

For example, rearranging A as (3,2,1,4) gives \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor=\left\lfloor\frac52\right\rfloor+\left\lfloor\frac32\right\rfloor+\left\lfloor\frac52\right\rfloor=5.

No matter how A is rearranged, the value of \displaystyle \sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor is at least 5, so the answer is 5.