1167 Minimum Cost to Connect Sticks

1 題目

You have some 

sticks

 with positive integer lengths.

You can connect any two sticks of lengths 

X

 and 

Y

 into one stick by paying a cost of 

X + Y

.  You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given 

sticks

 into one stick in this way.

Example 1:

Input: sticks = [2,4,3]
Output: 14
           

Example 2:

Input: sticks = [1,8,3,5]
Output: 30
           

2 嘗試解

2.1 分析

給定一組正數sticks，每次操作可以将其中兩個正數X和Y合并，操作的代價為X+Y。問要合并所有正數使得最後僅有一個正數剩餘，所需的最小操作代價。

每次操作減少一個數，是以共需要sticks.size()-1次操作。考慮sticks = [1,8,3,5]，越早合并的數，被重複計算的次數越多。是以我們希望長度短的早合并，長度長的晚合并。即每次取數組中最小的兩個數合并。

2.2 代碼

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int,vector<int>,greater<int>> saver;
        int result = 0;
        for(auto stick : sticks)
            saver.push(stick);
        while(saver.size() > 1){
            int first = saver.top();
            saver.pop();
            int second = saver.top();
            saver.pop();
            result += first + second;
            saver.push(first+second);
        }
        return result;
    }
};
           

3 标準解

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
      priority_queue<int, vector<int>, greater<int>> qu(sticks.begin(), sticks.end());
      int result = 0;
      while (qu.size() > 1) {
        int a = qu.top(); qu.pop();
        int b = qu.top(); qu.pop();
        result += a + b;
        qu.push(a + b);
      }
      return result;
    }
};