| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 5 | 2 | 1 | 100.000% |
Little C has $n$ books, each with a weight, and he decides to merge them into a pile.
Each time when Little C merges, he can put one pile of books on top of another to merge them into one pile. If Little C puts the $i$-th pile of books on top of the $j$-th pile of books, the energy Little C needs to consume is the weight of the $i$-th pile of books plus the wear value of the two piles of books.
Initially, each book is in its own pile and the wear values are all 0ドル$. Whenever Little C merges two piles of books, the wear value of the new pile of books formed is twice the larger of the wear values of the two piles of books before merging, plus one. The weight of the new pile of books is the sum of the weights of the two piles of books before merging.
Your task is to design a merging order to minimize the total energy consumption of Little C and output the minimum total energy consumption.
This problem has multiple test data sets.
The first line of the input contains an integers $t,ドル which represents the number of test data sets.
Then, each set of test data is given as input in order. For each set of test data:
The first line of input contains a positive intege $n,ドル which represents the number of books.
The second line of input contains $n$ positive integers $w_1,w_2,\dots,w_n,ドル where $w_i$ represents the weight of the $i$-th book.
For each set of test data, output a line containing an integer, representing the minimum total energy consumption.
For all test data, it is guaranteed that: 1ドル \leq t\leq 10,1\leq n\leq 100,1\leq w_i\leq 10^9$.
1 4 1 1 1 1
6
If Little C combines the four books in pairs and then combines the two pairs into one, the energy consumption of the first two merging operations is 1ドル$ each, and in the third time, a pile of books with weight of 2ドル$ is placed on top of the other pile. The wear value of the two piles of books is 1ドル$ each, and the energy consumption is 2ドル + 1 + 1 = 4$. Therefore, if Little C chooses this plan, the total energy consumption is only 1ドル + 1 + 4 = 6$. It can be proved that in the above sample, 6ドル$ is the minimum total energy consumption.
samples.zip