以最低成本连接 n 根绳索
有N根给定长度的绳索。我们必须与他们建立联系。将一根绳子与另一根绳子连接起来的成本是它们长度的总和。我们的目标是以最小的成本连接N条绳索。
这个问题可以使用堆树来解决。我们将创建最小堆以首先插入所有不同的长度，然后从最小堆中删除最小和第二个最小项，连接它们并再次插入到堆树中。当堆只包含一个元素时，我们可以停止该过程并以最小的成本获得连接的绳索。
输入和输出
Input:
The lengths of the ropes: {4, 3, 2, 6, 5, 7, 12}
Output:
总最低成本： 103算法
findMinCost(array, n)
输入-绳索长度列表，列表中的条目数。
输出-削减的最低成本。
Begin
minCost := 0
fill priority queue with the array elements, (greater value is higher priority)
while queue is not empty, do
item1 := get item from queue and delete from queue
item2 := get item from queue and delete from queue
minCost := minCost + item1 + item2
add (item1 + item2) into the queue
done
return minCost
End示例
#include输出结果#include #include using namespace std; int findMinimumCost(int arr[], int n) { //优先级队列设置为值越大，优先级越高 priority_queue< int, vector , greater >queue(arr, arr+n); int minCost = 0; while (queue.size() > 1) { //当队列有多个元素时 int item1 = queue.top(); //item1是最短的元素 queue.pop(); int item2 = queue.top(); //item2比item1大但比其他短 queue.pop(); minCost += item1 + item2; //连接绳索并将它们添加到队列中 queue.push(item1 + item2); } return minCost; } int main() { int ropeLength[] = {4, 3, 2, 6, 5, 7, 12}; int n = 7; cout << "总最低成本： " << findMinimumCost(ropeLength, n); }
总最低成本： 103