a996. 加總的代價 - 旦旦解題農場

內容

原題名為 Add-All

做加法要付出的代價（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$ 個數加起來直到剩下一個數

請問最小的代價為何？

輸入說明

本題多個測資點，每個測資點中單筆測資

每個測資點中，第一行是一個正整數 $T$，代表接下來有 $T$ 個問題

每個問題中第一行是一個正整數 $N$ 代表有幾個數要相加

第二行有 $N$ 個以空白隔開的正整數

代表欲操作的陣列

輸出說明

輸出題目所求之最小代價，每個輸出之間以換行隔開

範例輸入

範例輸出

9
19

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (15%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (50%): 1.0s , <10M

提示：

對於所有測資：$T = 10$，$1 \leq N \leq 10^5$，$1 \leq$ 數字 $\leq 1000$

測資 $\text #00$：$1 \leq N \leq 10$

測資 $\text #01$：$1 \leq N \leq 10^2$

測資 $\text #02$：$1 \leq N \leq 10^3$

測資 $\text #03$：$1 \leq N \leq 10^4$

測資 $\text #04$：無特別限制

禁止使用 $\text{getchar()}$

標籤:

STL greedy

出處:

UVA10954 [管理者：

frankie (34104)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」