数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过重复合并任意相邻元素来减少数组的最小成本
在 C++ 中，我们有一个 pop() 函数用于从开头删除元素。top() 函数返回 priority_queue 的第一个元素的引用，而 push() 函数用于在其上插入元素。优先队列是数据结构的一部分，它根据元素的值来管理元素。
在本文中，我们将学习通过重复合并任意相邻元素来减少数组的最小成本。
让我们从本文中举一个例子 -
我们将绘制大小为 4 的数组，并重复添加相邻元素。
语法
程序中使用的以下语法 -
priority_queue< int, vector<int>, greater<int> >name_of_queue;
解释
这是默认情况下 C++ 创建优先队列的最大堆的最小堆的语法。
int - 这是一个 STL 容器，它收集相同类型的对象。
greater<int> - 这是一个比较器类，用于比较用户定义类的对象。
算法
我们将从名为‘iostream’、‘queue’ 和 ‘vector’ 的头文件开始程序。
之后，我们定义了一个名为 ‘findMinimumCost’ 的全局函数，它接受两个整数值参数，即 ‘arr[]’ 和 ‘n’，以验证其最小成本，以通过合并任何相邻元素来减少数组。
然后我们开始将 cost 变量初始化为 ‘0’，稍后将添加到 ‘cost’ 变量中，并定义优先队列 ‘ab’ 来存储数组的元素。
我们使用 for 循环遍历输入数组并将每个元素添加到优先队列 ‘ab’ 中。
然后我们将创建一个 while 循环来检查优先队列 ‘ab’ 的条件。如果它具有超过 1 个元素，则它将从队列中提取两个最小的元素。
通过使用 top() 和 pop() 预定义函数提取元素后，我们将总和添加到成本中，并将总和插入到队列中，这将通过合并相邻元素来减少最小成本。
处理完所有条件后，函数将返回 ‘cost’ 的结果值。
现在我们将开始主函数并将值 ‘4’ 存储到 ‘n’ 变量中，该变量表示变量的大小。接下来，将数组元素存储在 ‘arr[]’ 变量中。
我们将调用 ‘findMinimumCost()’ 函数，该函数接受两个参数 ‘arr’ 和 ‘n’ 以传递输入，并且此函数调用存储到变量 ‘minimumCost’ 中。
最后，我们使用 ‘minimumCost’ 变量打印语句 “减少数组的最小成本：”。
示例
在此程序中，我们将计算通过重复合并任意相邻元素来减少数组的最小成本。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int findMinimumCost(int arr[], int n) {
int cost = 0;
priority_queue<int, vector<int>, greater<int>> ab;
// add elements of the array to the priority queue
for (int i = 0; i < n; i++) {
ab.push(arr[i]);
}
// reducing the array by merging adjacent elements
while (ab.size() > 1) {
int x = ab.top();
ab.pop();
int y = ab.top();
ab.pop();
int sum = x + y;
cost += sum;
ab.push(sum);
}
return cost;
}
int main() {
int n = 4;
// size of array
int arr[] = {9, 10, 11, 12};
int minimumCost = findMinimumCost(arr, n);
cout << "Minimum cost of reducing the array: " << minimumCost << endl;
return 0;
}
输出
Minimum cost of reducing the array: 84
结论
我们探讨了通过重复合并任意相邻元素来减少数组的最小成本的概念。我们看到了在此程序中 pop() 和 top() 之间的区别。此技术主要用于诸如负载平衡、操作系统中的优先级调度、中断处理和数据压缩等应用程序中。
381 次查看
