[NOIP2004 Advanced Group] Merging Fruits / [USACO06NOV] Fence Repair G

Problem Description

In an orchard, Duoduo has already knocked down all the fruits and divided them into different piles according to their types. Duoduo decides to merge all the fruits into one pile.

Each time, Duoduo can merge two piles together, and the effort consumed equals the sum of the weights of the two piles. It can be seen that after (n-1) merges, only one pile remains. The total effort Duoduo consumes in merging fruits is the sum of the effort for each merge.

Since it takes a lot of effort to carry the fruits home, Duoduo wants to save as much effort as possible. Assuming each fruit wieghs 1, and given the number of fruit types and the count for each type, your task is to design a merging sequence that minimizes the total effort, and output that minimal effort value.

For example, there are 3 types of fruits with counts 1, 2, and 9. First merge the piles of 1 and 2 to get a new pile of 3, costing 3 effort. Then merge the new pile with the original pile of 9 to get a pile of 12, costing 12 effort. So total efffort = 3 + 12 = 15. It can be proved that 15 is the minimal effort.

Input Format

There are two lines. The first line contains an integer (n) ((1 \leq n \leq 10000)), the number of fruit types. The second line contains (n) integers separated by spaces, where the (i)-th integer (a_i) ((1 \leq a_i \leq 20000)) is the count of the (i)-th fruit type.

Output Format

Output a single integer, the minimal total efffort. It is guaranteed that this value is less than (2^{31}).

Sample #1

Sample Input #1

3
1 2 9

Sample Output #1

15

Hint

• For 30% of the data, (n \leq 1000).
• For 50% of the data, (n \leq 5000).
• For all data, (n \leq 10000).

Code Example

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x, total_cost = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        pq.push(x);
    }
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int sum = a + b;
        total_cost += sum;
        pq.push(sum);
    }
    cout << total_cost << endl;
    return 0;
}