当前位置：首页 > news >正文

基础实验4-2.7 修理牧场

news 2025/5/30 13:06:47

基础实验4-2.7 修理牧场

分数 25

全屏浏览

切换布局

作者 DS课程组

单位浙江大学

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要 n 块木头，每块木头长度为整数 li 个长度单位，于是他购买了一条很长的、能锯成 n 块的木头，即该木头的长度是 li 的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为 20 的木头锯成长度为 8、7 和 5 的三段，第一次锯木头花费 20，将木头锯成 12 和 8；第二次锯木头花费 12，将长度为 12 的木头锯成 7 和 5，总花费为 32。如果第一次将木头锯成 15 和 5，则第二次锯木头花费 15，总花费为 35（大于 32）。

请编写程序帮助农夫计算将木头锯成 n 块的最少花费。

输入格式:

输入首先给出正整数 n（≤104），表示要将木头锯成 n 块。第二行给出 n 个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成 n 块的最少花费。

输入样例:

8
4 5 1 2 1 3 1 1

输出样例:

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

解题思路：

问题理解：
- 我们有 n 段木头，目标是通过不断将木头切成小段，直到分成指定的 n 段。每次切割的代价是当前木头的长度，因此我们希望每次切割代价最小。
- 具体地，可以用一种贪心策略：每次将最短的两段木头拼接起来，减少总的切割费用。
哈夫曼树模型：
- 每次选择长度最小的两段木头进行拼接，形成一段新的木头，花费为这两段木头的总长度。然后，将新的木头加入可选择的木头段中，重复这个过程直到所有木头拼接成一个整体。
- 为了高效地找到最短的两段木头，我们可以使用**优先队列（最小堆）**来实现。
贪心策略：
- 每次从剩下的木头中选出两段最短的木头进行拼接，将它们的长度相加，并将结果插回到队列中，重复此过程直到没有木头可以再拼接。

具体步骤：

将所有木头的长度存入优先队列（最小堆）。
每次从队列中取出两个最短的木头段，将它们拼接（相加长度），累加代价。
将新形成的木头段再次放入队列，继续上述操作直到所有木头拼接完成。
最终累加的代价就是最小的锯木代价。

代码实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {int n;cin >> n;// 优先队列（最小堆），用于存储木头段的长度priority_queue<int, vector<int>, greater<int>> pq;// 读取每段木头的长度for (int i = 0; i < n; ++i) {int length;cin >> length;pq.push(length);}int totalCost = 0;// 每次取出最短的两段木头，合并并计算花费while (pq.size() > 1) {int first = pq.top(); pq.pop();int second = pq.top(); pq.pop();int cost = first + second;totalCost += cost;// 将新的木头段长度插入优先队列pq.push(cost);}// 输出最少的总花费cout << totalCost << endl;return 0;
}

代码解析：

优先队列的使用：
- 我们使用 priority_queue<int, vector<int>, greater<int>> pq 来实现最小堆。
- priority_queue 是 C++ 标准库中提供的优先队列容器，默认是最大堆，但通过第三个模板参数 greater<int> 可以将其改为最小堆。
将所有木头段长度存入优先队列：
- pq.push(length) 将每段木头长度加入优先队列中。
- 由于优先队列是最小堆，每次从队列取出的元素都是当前最小的木头段。
贪心算法的核心：
- 每次从优先队列中取出最短的两段木头 first 和 second，将它们相加，累加当前的花费 cost，并将新形成的木头段长度重新插入优先队列中。
- 这个过程重复进行，直到优先队列中只有一段木头为止。
总花费计算：
- totalCost += cost 累加每次合并木头的花费，最终输出这个累加值。

知识点解释：

优先队列（最小堆）：
- 优先队列是一种抽象数据结构，可以快速地找到最大或最小元素。在这道题中，我们使用最小堆来快速找到当前最短的两段木头。
- 操作 push() 和 pop() 的时间复杂度是 O(log n)，因此整体复杂度是 O(n log n)，适合处理 n ≤ 10^4 的情况。
贪心算法：
- 贪心算法是一种逐步选择最优解的策略。在这道题中，每次都选择当前最小的两段木头进行拼接，确保当前步骤的最优性，从而保证整个过程的最小花费。
哈夫曼编码原理：
- 这道题与哈夫曼编码问题类似，本质上是通过最小化合并代价来构建最优二叉树。哈夫曼编码的思想也是通过不断将最小的元素组合起来，构造出最小的代价。

时间复杂度：

时间复杂度： 每次插入和删除操作的时间复杂度是 O(log n)，总共有 n 段木头，每次合并两个木头段需要进行一次插入和删除操作，因此总时间复杂度为 O(n log n)。
空间复杂度： 使用了优先队列存储木头段的长度，空间复杂度为 O(n)。

总结：

通过贪心算法和优先队列，我们能够高效地解决这个最小锯木花费问题。
使用最小堆来确保每次总是选择最短的两段木头进行拼接，最终得到最小的切割成本

当然我们还可以用其他的办法

使用数组实现最小堆的贪心法

代码实现：

#include <iostream>
#include <vector>
using namespace std;// 上滤操作
void siftUp(vector<int>& heap, int idx) {while (idx > 0) {int parent = (idx - 1) / 2;if (heap[idx] >= heap[parent]) break;  // 如果当前节点不小于父节点，停止上滤swap(heap[idx], heap[parent]);  // 否则交换当前节点与父节点idx = parent;  // 继续向上调整}
}// 下滤操作
void siftDown(vector<int>& heap, int idx) {int n = heap.size();while (2 * idx + 1 < n) {  // 当有左子节点时继续int left = 2 * idx + 1;int right = 2 * idx + 2;int smallest = left;// 如果右子节点存在并且比左子节点小if (right < n && heap[right] < heap[left]) {smallest = right;}// 如果当前节点已经小于等于最小的子节点，停止下滤if (heap[idx] <= heap[smallest]) break;// 否则交换当前节点与最小的子节点swap(heap[idx], heap[smallest]);idx = smallest;  // 继续向下调整}
}// 插入新元素到堆中
void heapInsert(vector<int>& heap, int value) {heap.push_back(value);  // 将新元素插入到堆尾siftUp(heap, heap.size() - 1);  // 上滤操作调整堆
}// 从堆中取出最小元素
int heapExtractMin(vector<int>& heap) {int minValue = heap[0];  // 取出堆顶元素（最小值）heap[0] = heap.back();  // 用最后一个元素替换堆顶heap.pop_back();  // 删除最后一个元素if (!heap.empty()) {siftDown(heap, 0);  // 下滤操作调整堆}return minValue;
}// 贪心算法：使用最小堆求解最少锯木花费
int minCostToCutWood(vector<int>& woodLengths) {vector<int> heap;// 将所有木头段长度插入最小堆for (int length : woodLengths) {heapInsert(heap, length);}int totalCost = 0;// 不断从最小堆中取出最小的两段木头并合并while (heap.size() > 1) {int first = heapExtractMin(heap);  // 取出最小的木头段int second = heapExtractMin(heap); // 取出第二小的木头段int cost = first + second;  // 合并这两段木头的花费totalCost += cost;// 将合并后的新木头段插入最小堆heapInsert(heap, cost);}return totalCost;
}int main() {int n;cin >> n;vector<int> woodLengths(n);// 读取每段木头的长度for (int i = 0; i < n; ++i) {cin >> woodLengths[i];}// 使用最小堆计算最少的总花费int result = minCostToCutWood(woodLengths);// 输出最少的总花费cout << result << endl;return 0;
}

代码解析：

堆操作函数：
- siftUp：调整插入新元素后堆的顺序，从下往上调整，确保父节点小于等于子节点。
- siftDown：调整删除堆顶元素后堆的顺序，从上往下调整，确保堆的最小堆性质（父节点小于等于子节点）。
核心操作：
- heapInsert：插入一个新元素到堆尾，然后调用 siftUp 函数保持最小堆的性质。
- heapExtractMin：删除堆顶元素（最小值），将堆尾元素移到堆顶，并调用 siftDown 函数调整堆结构。
贪心算法：
- 每次取出堆中的两个最小值，合并它们，并将合并后的长度重新插入堆。
- 总花费是合并过程中所有长度的总和。

时间复杂度：

插入操作和删除最小值操作 的时间复杂度都是 O(log n)，因为堆的高度为 O(log n)。
总共进行 n-1 次合并，每次涉及两个堆操作，所以整体复杂度为 O(n log n)，与 priority_queue 的复杂度相同。

总结：

这种手动实现的方式不依赖 C++ 的 priority_queue，而是通过数组和堆操作函数实现了最小堆的核心功能。

在C++中，函数参数加 `&` 表示传引用，而不加 `&` 表示传值。这两种方式的区别在于，传引用能够直接修改传入的对象，而传值则是在函数内部创建该对象的副本，函数对副本的修改不会影响原始对象。

在你的代码中，siftUp 函数的参数 vector<int>& heap 加了 &，表示传引用，目的是直接修改传入的堆，即 heap。

为什么要加 `&`：

避免不必要的拷贝：
- 如果不加 &，即 void siftUp(vector<int> heap, int idx)，这意味着当你调用 siftUp 函数时，会把整个 heap 复制一份，生成一个新的副本传递给函数。
- 这会导致性能开销，尤其当 heap 很大的时候，拷贝整个数组会耗费大量的时间和内存。
直接修改原始数据：
- 你希望在 siftUp 函数中修改原始的 heap。如果传的是副本，修改的只是副本，而不会影响调用函数中的原始 heap。
- 通过传引用，siftUp 函数中对 heap 的任何修改都会作用到原始的 heap 上，这样可以达到你期望的效果。

示例对比：

传引用（有 &）：

void siftUp(vector<int>& heap, int idx) {heap[idx] = 10;  // 修改传入的 heap 的值
}int main() {vector<int> heap = {1, 2, 3};siftUp(heap, 1);cout << heap[1];  // 输出 10，因为 heap 被修改了
}

传引用（有 &）：

void siftUp(vector<int> heap, int idx) {heap[idx] = 10;  // 修改的是 heap 的副本
}int main() {vector<int> heap = {1, 2, 3};siftUp(heap, 1);cout << heap[1];  // 输出 2，因为原始 heap 没有被修改
}