POJ 3253 Fence Repair C++ STL multiset 可解 (同51nod 1117 聪明的木匠)-白红宇

POJ 3253 Fence Repair C++ STL multiset 可解 (同51nod 1117 聪明的木匠)

阅读量：793 次

发布时间：2023-03-03

本文共 1089 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到一种切割顺序，使得总费用最小。每次切割的费用等于被切割木头的长度。我们的目标是通过贪心算法，选择每次切割最小的两个木头，从而最小化总费用。

方法思路

我们可以使用最小堆来实现这个贪心算法。每次从堆中取出两个最小的元素，计算它们的和，并将这个和重新放回堆中，同时记录总费用。这样可以确保每次切割的费用最小化，从而总费用最小化。

具体步骤如下：

将所有木头的长度放入一个最小堆中。

初始化总费用为0。

当堆中有超过一个元素时，重复以下步骤：a. 取出堆顶的两个最小元素，记为a和b。b. 计算它们的和s = a + b。c. 将s加入堆中，并将s加到总费用中。

当堆中只剩一个元素时，循环结束。

输出总费用。

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    int n;    cin >> n;    priority_queue

, greater

> heap; for(int i = 0; i < n; ++i) { int x; cin >> x; heap.push(x); } int ans = 0; while(heap.size() >= 2) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); int s = a + b; ans += s; heap.push(s); } cout << ans << endl; return 0;}

代码解释

读取输入：首先读取输入的木头数量n，然后读取每个木头的长度。

初始化最小堆：将所有木头的长度放入一个最小堆中，以便每次都能快速获取最小的两个元素。

循环处理堆：在堆中有超过一个元素时，循环处理：

取出堆顶的两个最小元素。

计算它们的和，并将这个和重新放回堆中。

记录总费用。

输出结果：当堆中只剩一个元素时，输出总费用。

这种方法利用了贪心算法，每次都选择最优的切割顺序，从而确保总费用最小化。使用最小堆保证了每次操作的效率，使得总时间复杂度为O(N log N)。

转载地址：http://cfxfk.baihongyu.com/

你可能感兴趣的文章