68 . Add all

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

會寫程式的羊
咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩

User's AC Ratio

88.5% (23/26)

Submission's AC Ratio

62.1% (36/58)

Tags

Algo Algo25_a

Description

是的，題目名稱就是你要做的任務：把一些數加起來。但是這對你來說一定是太簡單了，所以讓我們加一些東西在裡面。

做加法要付出的代價（cost） 定義為這$2$個數的總和，所以要加 $1$ 和 $10$ 所需付出的代價為 $11$ 。假如你想要加 $1$, $2$ 和 $3$，那麼有以下幾種方法：

$1 + 2 = 3, cost = 3$
$3 + 3 = 6, cost = 6$
$Total = 9$ 		$1 + 3 = 4, cost = 4$
$2 + 4 = 6, cost = 6$
$Total = 10$ 		$2 + 3 = 5, cost = 5$
$1 + 5 = 6, cost = 6$
$Total = 11$

我希望你已經瞭解你的任務，就是把 $N$ 個數加起來使得付出的代價最少。

Input Format

輸入的第一行包含一個正整數 $T (T \leq 10)$，代表測試資料的數量

每組測試資料開始有一個正整數 $N(2\leq N \leq 10^ 5)$ ，接下來有 $N$ 個正整數（均小於$10^ 8$）。

請參考範例輸入。

對於$20\%$的測試資料保證$1\leq N\leq 20$
對於$50\%$的測試資料保證$1\leq N\leq 1000$
對於$100\%$的測試資料保證$1\leq N\leq 10^ 5$，所有數字均小於$ 10^ 8 $

Output Format

對每一組測試資料輸出一列，相加這 $N$ 個數付出的代價最少是多少。

Sample Input 1

2
3
1 2 3
4
1 2 3 4

Sample Output 1

9
19

Hints

題目來源： UVA

Problem Source

NEOJ Problem 70

Subtasks

No. Testdata Range Constraints Score
1 0~1 20
2 0~4 30
3 0~9 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 65536 1 2 3
1 3000 65536 65536 1 2 3
2 3000 65536 65536 2 3
3 3000 65536 65536 2 3
4 3000 65536 65536 2 3
5 3000 65536 65536 3
6 3000 65536 65536 3
7 3000 65536 65536 3
8 3000 65536 65536 3
9 3000 65536 65536 3
Submit
Back to Top