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;
    }
};