資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
