题目链接

Fence Repair POJ - 3253

思路

贪心，霍夫曼树，使用小根堆维护每次去最小值和次小值之和计入贡献。

注意数据范围答案开long long

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <queue>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    priority_queue<int, vector<int>, greater<int> > sm;
    while (n--) {
        int x;
        scanf("%d", &x);// don't forget &
        sm.push(x);
    }
    long long ans = 0;
    while (sm.size() != 1) {
        int x = sm.top();
        sm.pop();
        int y = sm.top();
        sm.pop();
        ans += x + y;
        sm.push(x + y);
    }
    printf("%lld", ans);
    return 0;
}