合并果子 Python解法 贪心
题目描述
合并石子,但不要求相邻
每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。
样例
3
1 2 9
15
算法1
(贪心) $O(log(n!))$
huffman树问题,每次选权值最小的两个数
最优解对应的树有这样的性质:权值最小的两个点,深度一定要最深,否则和权值最深的点交换,代价变小
f(n)最优是选两个最小的加f(n-1),f(n-1)单独考虑也是选两个最小的再加f(n-2),那么每一步都是选两个最小的
时间复杂度 $O(log(n!))$
- 建堆$O(n)$
- n次遍历,每次遍历调整堆:$O(logs)$ (s为堆的节点个数,初始为n,后续不断减至2)
$logn + log(n - 1) + … + log2 = log(n!)$ - $log(n!) < nlogn$
粗略计算$O(log(n!))$
Python 代码
import heapq
n = int(input())
nums = list(map(int, input().strip().split()))
heapq.heapify(nums)
res = 0
while len(nums) > 1:
a = nums[0]
heapq.heappop(nums)
b = nums[0]
heapq.heappop(nums)
res += a + b
heapq.heappush(nums, a + b)
print(res)