Límite de tiempo: 1000 ms
Límite de memoria: 256 MB

En un huerto, se han recolectado todas las frutas y clasificado en diferentes montones según su variedad. El objetivo es combinar todos los montonse en uno solo. En cada operación de fusión, se unen dos montones y el costo energético equivale a la suma de las cantidades de ambos montones. Tras realizar n-1 fusiones, quedará un único montón. La energía total consumida corresponde a la suma de los costos de cada fusión individual.

Dado que el número de frutas por montón es conocido, el desafío consiste en determinar el orden óptimo de fusiones que minimice el gasto energético total. Cada fruta tiene peso unitario.

Ejemplo: Con 3 montones de tamaños 1, 2 y 9: primero se futionan 1 y 2 obteniendo un montón de 3 (costo: 3), luego se fusiona este con 9 obteniendo 12 (costo: 12). Total = 15.

Formato de entrada y salida

Entrada: Dos líneas. La primera contiene un entero n (1 ≤ n ≤ 10000) que indica el número de tipos de fruta. La segunda contiene n enteros separados por espacios, donde el i-ésimo entero ai (1 ≤ ai ≤ 20000) representa la cantidad de frutas del i-ésimo tipo.

Salida: Una sola línea con un entero que representa el mínimo gasto energético. Se garantiza que el valor es menor que 2^31.

Ejemplo

Entrada:

3
1 2 9

Salida:

15

Solución 1: Uso de multiset ordenado

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

int main(){
    multiset<int> montones;
    int cantidad;
    cin >> cantidad;
    
    for(int i = 0; i < cantidad; i++){
        int peso;
        cin >> peso;
        montones.insert(peso);
    }
    
    int energiaTotal = 0;
    
    while(montones.size() > 1){
        auto primero = montones.begin();
        int menor1 = *primero;
        montones.erase(primero);
        
        auto segundo = montones.begin();
        int menor2 = *segundo;
        montones.erase(segundo);
        
        int combinado = menor1 + menor2;
        energiaTotal += combinado;
        montones.insert(combinado);
    }
    
    cout << energiaTotal;
    return 0;
}

Solución 2: Arreglo ordenado con inserción binaria

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

int main(){
    int n;
    cin >> n;
    
    vector<int> pilas(n);
    for(int i = 0; i < n; i++){
        cin >> pilas[i];
    }
    
    sort(pilas.begin(), pilas.end());
    
    long long costo = 0;
    
    while(pilas.size() > 1){
        int a = pilas[0];
        int b = pilas[1];
        
        pilas.erase(pilas.begin());
        pilas.erase(pilas.begin());
        
        int fusion = a + b;
        costo += fusion;
        
        auto pos = lower_bound(pilas.begin(), pilas.end(), fusion);
        pilas.insert(pos, fusion);
    }
    
    cout << costo;
    return 0;
}

Solución 3: Cola de prioridad con functor personalizado

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

struct ComparadorMinimo {
    bool operator()(const int& x, const int& y) const {
        return x > y;
    }
};

int main(){
    priority_queue<int, vector<int>, ComparadorMinimo> cola;
    
    int total;
    cin >> total;
    
    while(total--){
        int valor;
        cin >> valor;
        cola.push(valor);
    }
    
    int acumulado = 0;
    
    while(cola.size() > 1){
        int minA = cola.top();
        cola.pop();
        int minB = cola.top();
        cola.pop();
        
        int mezcla = minA + minB;
        acumulado += mezcla;
        cola.push(mezcla);
    }
    
    cout << acumulado;
    return 0;
}