原题：https://fjnuacm.top/d/junior/p/369?tid=6301e681027d8fe886628d9d

感觉之前写得太蠢了就重新写一下（

题意

每次把最小的两个拿出来合并并将数量作为本次体力消耗，输出最小体力消耗值。

思路1

显然，我们只需边枚举边排序，考虑到数据范围够小，暴力是完全可行的。

时间复杂度：$O(n \log n) - O(n^2 \log n)$

对应AC代码

#include <bits/stdc++.h>
​
using namespace std;
​
int d[20001];
​
int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> d[i];
    sort(d, d + n);
    int ans = 0;
    for(int i=1;i<n;i++){
        d[i] += d[i - 1];
        ans += d[i];
        sort(d + i, d + n);
    }
    cout << ans << endl;
}

思路2

不难发现，上面暴力的做法无非就是两个步骤：①排序 ②取最小两个加起来放回去

很巧的是，这些步骤完全可以使用封装好的堆结构来实现。

时间复杂度和上述暴力方法完全一致。

时间复杂度：$O(n \log n) - O(n^2 \log n)$

对应AC代码

import java.util.*;
​
public class Main{
​
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int n = scanner.nextInt();
        for(int i=0;i<n;i++) queue.offer(scanner.nextInt());
        int ans = 0;
        while(true){
            if(queue.isEmpty()) break;
            int a = queue.poll();
            if(queue.isEmpty()) break;
            int b = queue.poll();
            queue.offer(a + b);
            ans += a + b;
        }
        System.out.println(ans);
    }
}

堆 = 暴力（暴论