Given n piles of fruits with different weights, merge them into a single pile by repeatedly combining two piles at a time. Each merge operation consumes energy equal to the sum of the two piles' weights. The goal is to determine the merge sequence that minimizes total energy consumption.

For example, with piles weighing 1, 2, and 9 units:

• Merge piles 1 and 2 (cost: 3), resulting in piles [3, 9]
• Merge piles 3 and 9 (cost: 12), total cost = 3 + 12 = 15

Input Format The first line contains integer n (1 ≤ n ≤ 10000), the number of fruit piles. The second line contains n integers representing pile weights.

Output Format Print the minimum total energy cost.

Sample Input

3
1 2 9

Sample Output

15

Solution Approach A min-heap (priority queue) efficiently selects the two smallest piles for merging at each step. This greedy strategy ensures optimality by always combining the lightest available piles first.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int pileCount;
    cin >> pileCount;
    
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int i = 0; i < pileCount; i++) {
        int weight;
        cin >> weight;
        minHeap.push(weight);
    }
    
    int totalCost = 0;
    while (minHeap.size() > 1) {
        int first = minHeap.top();
        minHeap.pop();
        int second = minHeap.top();
        minHeap.pop();
        
        int mergeCost = first + second;
        totalCost += mergeCost;
        minHeap.push(mergeCost);
    }
    
    cout << totalCost << endl;
    return 0;
}

Constraints

• 30% of test cases: n ≤ 1000
• 50% of test cases: n ≤ 5000
• 100% of test cases: n ≤ 10000
• Output guaranteed to be less than 2^31