$$\color{Red}{合并果子 详细题解=三语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

可以对比我的非常详细的石子合并题解（区间DP）

这道题没有限制只能相邻的合并，那么我们每次选取最小的两个合并即可。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, N = 10010;
    static PriorityQueue<Integer> q = new PriorityQueue<Integer>();

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) q.add(Integer.parseInt(s2[i]));
        int res = 0;
        while (q.size() > 1){
            int a = q.remove();
            int b = q.remove();
            q.add(a + b);
            res += a + b;
        }
        System.out.println(res);
    }
}

python3

import heapq
n = int(input())
q = list(map(int, input().split()))
heapq.heapify(q)

res = 0 
while len(q) > 1:
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    heapq.heappush(q, a + b)
    res += a + b
print(res)

C++

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

int main()
{
    int n, x;
    priority_queue <int, vector<int>, greater<int>> heap;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        scanf("%d", &x);
        heap.push(x);
    }

    int ans = 0;
    while(heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        ans += a + b;
        heap.push(a + b);
    }

    cout << ans << endl;
    return 0;
}