Question e: merged fruit -noip2004tgt2

Title Description
In an orchard , Dodo has beaten all the fruit down , And according to different kinds of fruits, they are divided into different heaps . Duoduo decides to combine all the fruits into a pile . Every merger , Duoduo can combine the two piles of fruit , The energy consumed is equal to the sum of the weight of two heaps of fruits . It can be seen that , All the fruits pass by n-1 After the merger , There's only one pile left . Duoduo's total energy consumed during fruit merging is equal to the sum of energy consumed during each merging .
Because I have to work hard to carry these fruits home , Therefore, Duoduo should save energy as much as possible when merging fruits . Suppose that each fruit weighs 1, And we know the number of kinds of fruit and the number of each kind of fruit , Your task is to design a sequence plan for the merger , To minimize the amount of physical effort expended , And output this minimum energy cost .
For example, there are 3 Plant fruit , The order of numbers is 1,2,9. You can put 1、2 Heap merge , The number of new piles is 3, Expend physical energy for 3. next , Merge the new pile with the original third pile , And get a new pile , The number is 12, Expend physical energy for 12.
So a lot of energy =3+12=15. Can prove that 15 For the minimum physical cost .

Input
The input consists of two lines , The first line is an integer n(1<＝n<=10000), The number of kinds of fruit .
The second line contains n It's an integer , Separate... With spaces , The first i It's an integer ai(1<＝ai<=20000) It's No i The number of fruits planted .
Output
The output includes a line , This line contains only one integer , That's the minimum physical cost . Input data to ensure that the value is less than 2^31.

The sample input

3
1 2 9

Sample output

15

Ideas ： Priority queue .

#include <cstdio>
#include <queue>
using namespace std;

// Priority queue representing small top heap 
priority_queue<int, vector<int>, greater<int>> q;

int main() {
    
    int n, temp, x, y;
    while (scanf("%d", &n) != EOF) {
    
        int sum = 0;
        for (int i = 0; i < n; ++i) {
    
            scanf("%d", &temp);
            q.push(temp);
        }
        while (q.size() > 1) {
    
            x = q.top();
            q.pop();
            y = q.top();
            q.pop();
            q.push(x + y); // The sum of the two is added to the priority queue as a new number 
            sum += x + y;
        }
        q.pop();
        printf("%d\n", sum);
    }
    return 0;
}