题目描述

在这里插入图片描述

思路

每次取出人数最少的两个部落进行合并，使用小根堆可以以o(1)的时间复杂度取出最小值，每次取出两个元素，相加再加入队列中，当队列只剩一个元素时退出循环

代码

java版

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        PriorityQueue<Long> q = new PriorityQueue<>((a, b) -> Long.compare(a, b));
        int n = scan.nextInt();
        long ans = 0;
        for (int i = 0; i < n; i++) {
            q.offer(scan.nextLong());
        }

        while (q.size() > 1) {
            long f = q.poll(), s = q.poll();
            ans += f + s;
            q.offer(f + s);
        }

        System.out.println(ans);
        scan.close();
    }
}

python版

from heapq import heappush, heappop, heapify

n = int(input())
arr = list(map(int, input().split(" ")))
heapify(arr)
ans = 0
while len(arr) > 1:
    a, b = heappop(arr), heappop(arr)
    ans += a + b
    heappush(arr, a + b)
print(ans)

c++版

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    long ans = 0;
    int a;
    while ( n -- ){
        cin >> a;
        q.push(a);
    }

    while (q.size() > 1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        ans += a + b;
        q.push(a + b);
    }
    
    cout << ans;

    return 0;
}


// dcba