TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

96.0% (24/25)

Submission's AC Ratio

65.9% (60/91)

Description

在魔法名校霍格華茲中,除了天天都有的豐富課程以及刺激的實戰演練,還有許多一年舉辦一次的活動。這些活動不但可以增進學生之間的情誼,更可在無形之中推動學生的成長。

在這些活動中,其中一個是年年都會舉行的試膽大會。雖然名義上是試膽大會,不過這個活動的目的實際上是鍛練學生們的意志以及能力。不免俗地,試膽大會就是要兩個人一組參加。根據以往的經驗,只要兩人的實力愈相近,這場試膽大會帶給他們的進步就會愈大。事實上,如果兩人的實力值分別是$x,y$,那麼經過這次的試膽大會後他們就會分別進步$x+y-|x-y|$。

有一名剛進霍格華茲的實習老師接手了本年度的試膽大會流程安排的事務。當然,身為老師的他希望這場試膽大會帶過所有學生的成長最大,也就是說學生實力的總進步值最大。然而霍格華茲的學生人數不一定是個偶數,所以可能會剩下一個沒有伴的人沒辦法參加試膽大會。僅管落單的學生非常可憐,不過試膽大會時全校的老師都不會有空照顧這名學生,更別說陪他參加試膽大會了。在這種情況下,該落單的學生實力就完全不會進步。

比如說有四名學生,實力值分別是3, 1, 8, 4時,可將實力為1和實力為3的學生分成一組,實力為4和實力為8的學生分成一組。實力為1和3的學生分別進步了2,而實力為4和8的學生分別進步了8。故總進步值是20。這種分組方法是最佳的方法。

又比如說有五名學生,實力值分別是2, 8, 4, 1, 3。此時可將實力為2和實力為3的學生分成一組,實力為4和實力為8的學生分成一組,而使實力為1的學生落單。實力為2和3的學生分別進步了4,而實力為4和8的學生分別進步了8,而實力為1的學生沒有進步。故總進步值是24。這種分組方法也是最佳的方法。

給定這些學生的實力值,請你幫助實習老師找出所有學生的總進步值的最大值。

Input Format

第一行有一個正整數$T$代表測資筆數。
接下來每一個測資中的第一行都有一個正整數$N$,代表霍格華茲中學生的人數。接下來的一行會有$N$個不超過$10^ 9$的正整數,代表$N$名學生的實力值。

Output Format

對於每筆測資,請輸出學生實力總進步值的最大值。

Sample Input

2
4
3 1 8 4
5
2 8 4 1 3

Sample Output

20
24

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組10分,$T\leq 6, N\leq 10$
第二組10分,$T\leq 6, N\leq 2\times 10^ 3$,且$N$是偶數
第三組20分,$T\leq 6, N\leq 2\times 10^ 3$
第四組30分,$T\leq 6, N\leq 10^ 5$,且$N$是偶數
第五組30分,$T\leq 6, N\leq 10^ 5$

Problem Source

Problem Set / Description by Paupière
建國中學105學年度全國賽模擬賽pB

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 30
For Testdata: 4 ~ 4, Score: 30
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536