Problem Description

In a orchard, all fruits have been harvested and sorted into piles by type. The goal is to merge all piles into a single pile.

Each merge operation combines two piles, with energy consumption equal to the sum of their weights. After n-1 merges, only one pile remains. The total energy consumed is the sum of energy used in each merge.

The objective is to determine the merge sequence that minimizes total energy consumption, given that each fruit weighs 1 unit and the number of piles and their sizes are known.

For example, with three piles of sizes 1, 2, and 9:

• Merge piles 1 and 2: new pile size = 3, energy = 3
• Merge new pile (3) with pile 9: new pile size = 12, anergy = 12 Total energy = 3 + 12 = 15, which is optimal.

Input Format

First line: integer n (1 ≤ n ≤ 10000), number of piles. Second line: n integers separated by spaces, where each integer a_i (1 ≤ a_i ≤ 20000) represents a pile size.

Output Format

A single integer representing the minimum total energy consumption. Guaranteed to be less than 2^31.

Sample

Input:

3
1 2 9

Output:

15

Solution Approach

The optimal strategy is to always merge the two smallest available piles. This can be efficiently implemented using a min-heap (priority queue).

C++ Implementation

#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 totalEnergy = 0;
    
    while (minHeap.size() > 1) {
        int first = minHeap.top();
        minHeap.pop();
        int second = minHeap.top();
        minHeap.pop();
        
        int mergedWeight = first + second;
        totalEnergy += mergedWeight;
        minHeap.push(mergedWeight);
    }
    
    cout << totalEnergy << endl;
    return 0;
}

Alternative Array-Based Solution

To smaller constraints or educational purposes:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int piles[10010];
    
    for (int i = 0; i < n; i++) {
        cin >> piles[i];
    }
    
    sort(piles, piles + n);
    int energy = 0;
    
    while (n > 1) {
        // Merge two smallest piles
        piles[1] += piles[0];
        energy += piles[1];
        
        // Shift array to remove first element
        for (int j = 1; j < n; j++) {
            piles[j - 1] = piles[j];
        }
        n--;
        
        // Re-sort to maintain order
        sort(piles, piles + n);
    }
    
    cout << energy << endl;
    return 0;
}

Complexity Analysis

• Priority Queue Solutino: O(n log n) time complexity, O(n) space complexity
• Array Solution: O(n² log n) time complexity due to repeated sorting, O(n) space complexity

The priority queue implementation is preferred for the given constraints (n ≤ 10000).