洛谷P1334 瑞瑞的木板 题解 贪心+堆

题目链接：https://www.luogu.com.cn/problem/P1334

解题思路：

拆机就是合并的反过程，合并的时候肯定选择长度最短的两块合并。

所以贪心n-1次，每次选择最小的两块合并。

用一个最小堆来维护木块。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, a;
long long sum;
priority_queue<int, vector<int>, greater<int> > heap;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> a;
        heap.push(a);
    }
    for (int i = 1; i < n; i ++) {
        a = heap.top();
        heap.pop();
        a += heap.top();
        heap.pop();
        heap.push(a);
        sum += a;
    }
    cout << sum << endl;
    return 0;
}

洛谷P1334 瑞瑞的木板 题解 贪心+堆

原文：https://www.cnblogs.com/quanjun/p/12387488.html