P76062 合并货物 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76062，不要直接用于外站同名题。

解题思路

每次取出最轻的两堆合并，花费为二者之和，然后把合并后的新堆重新放入小根堆。

复杂度

时间 $O(n\log n)$，空间 $O(n)$。

易错点

新堆还要继续参与后续合并；答案可能超过 32 位整数。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    priority_queue<ll,vector<ll>,greater<ll>>h;
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        h.push(x);
    }
    ll total=0;
    while(h.size()>=2){
        ll a=h.top();
        h.pop();
        ll b=h.top();
        h.pop();
        ll s=a+b;
        total+=s;
        h.push(s);
    }
    cout<<total<<nl;
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。