Lintcode 1872 · Minimum Cost to Connect Sticks [Python]

本文主要是介绍Lintcode 1872 · Minimum Cost to Connect Sticks [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目在下方。读题目，有点儿费解，但是基本思路就是每次选择最小的棍子和第二小的棍子，加起来，丢回棍子堆里，然后继续重复，直到只剩下一个整的棍子。很容易想到用堆。

import heapq
class Solution:"""@param sticks: the length of sticks@return: Minimum Cost to Connect Sticks"""def MinimumCost(self, sticks):# write your code hereheap = []for idx, stk in enumerate(sticks):heapq.heappush(heap, stk)res = 0while len(heap) != 1:x = heapq.heappop(heap)y = heapq.heappop(heap)res += xres += ynewstk = x + yheapq.heappush(heap, newstk)#res += heap[0]return res

1872 · Minimum Cost to Connect Sticks
Algorithms
Medium
Accepted Rate
71%

DescriptionSolutionNotesDiscussLeaderboard
Description
In order to decorate your new house, you need to process some sticks with positive integer length.
You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. Due to the construction needs, you must connect all the bars into one.
Return the minimum cost of connecting all the given sticks into one stick in this way.
Please note that you can choose any order of sticks connection

1 \leq sticks.length \leq 10^41≤sticks.length≤10
4

1 \leq sticks[i] \leq 10^41≤sticks[i]≤10
4

Example
Example 1:

Input:
[2,4,3]
Output:
14
Explanation:
First connect 2 and 3 to 5 and cost 5; then connect 5 and 4 to 9; total cost is 14
Example 2:

Input:
[1,8,3,5]
Output:
30
Tags
Heap
Greedy

这篇关于Lintcode 1872 · Minimum Cost to Connect Sticks [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---