M18164: 剪绳子

greedy, huffman, http://cs101.openjudge.cn/practice/18164/

小张要将一根长度为L的绳子剪成N段。准备剪的绳子的长度为L1,L2,L3...,LN，未剪的绳子长度恰好为剪后所有绳子长度的和。

每次剪断绳子时，需要的开销是此段绳子的长度。

比如，长度为10的绳子要剪成长度为2,3,5的三段绳子。长度为10的绳子切成5和5的两段绳子时，开销为10。再将5切成长度为2和3的绳子，开销为5。因此总开销为15。

请按照目标要求将绳子剪完最小的开销时多少。

已知，1<=N <= 20000，0<=Li<= 50000

输入

第一行：N，将绳子剪成的段数。第二行：准备剪成的各段绳子的长度。

输出

最小开销

样例输入

3
2 3 5

样例输出

来源：cs101-2017 期末机考备选

与 05333: Fence Repair 一样。http://cs101.openjudge.cn/practice/05333

思路：剪绳子，实际上是 Huffman编码/树，https://zhuanlan.zhihu.com/p/42238580

python

# OJ18164
import sys
try: fin = open('test.in','r').readline
except: fin = sys.stdin.readline

n = int(fin())
import heapq
a = list(map(int, fin().split()))
heapq.heapify(a)
ans = 0
for i in range(n-1):
    x = heapq.heappop(a)
    y = heapq.heappop(a)
    z = x + y
    heapq.heappush(a, z)
    ans += z
print(ans)

bisect.insort时间复杂度？sorted时间复杂度？

bisect.insort函数的时间复杂度为O(N)，其中N是列表的长度。在最坏情况下，需要在列表中插入元素时，需要移动N个元素来完成插入操作。

sorted函数的时间复杂度为O(NlogN)，其中N是列表的长度。它使用的是Timsort算法（一种混合了插入排序和归并排序的排序算法），在平均情况下具有O(NlogN)的时间复杂度。

需要注意的是，这些时间复杂度是基于比较排序的情况。如果列表中的元素具有固定长度，可以使用线性时间复杂度的排序算法，如计数排序或基数排序，来优化排序过程。但对于一般的比较排序算法，以上给出的时间复杂度是适用的。

heapq时间复杂度？

heapq模块中的主要操作函数的时间复杂度如下：

heapify: 将列表转换为堆的时间复杂度为O(N)，其中N是列表的长度。
heappush: 向堆中插入元素的时间复杂度为O(logN)，其中N是堆的大小。
heappop: 从堆中弹出最小元素的时间复杂度为O(logN)，其中N是堆的大小。
heappushpop: 向堆中插入元素并弹出最小元素的时间复杂度为O(logN)，其中N是堆的大小。
heapreplace: 弹出最小元素并插入新元素的时间复杂度为O(logN)，其中N是堆的大小。

这些操作的时间复杂度都是基于二叉堆的实现方式。二叉堆是一种完全二叉树的数据结构，具有良好的堆特性，可以在O(logN)的时间内进行插入、删除最小元素等操作。

需要注意的是，以上给出的时间复杂度是基于堆的大小的，而不是输入列表的大小。因此，在使用heapq模块时，操作的时间复杂度与堆的大小相关，而不是与输入列表的大小相关。

python

#23-叶子涵-工院
import bisect
N=int(input())
ribbons=sorted(list(map(lambda x:-int(x),input().split())))
mini=0
for i in [0]*(N-1):
    A=ribbons.pop()
    B=ribbons.pop()
    mini-=A+B
    bisect.insort(ribbons,A+B)
print(mini)

【梁天书，2021年秋】题目头一次引入堆的概念，知道了这种数据结构。正向思考剪绳子的方法就是一定先把长的剪掉。由结果进行反演时，需要把最小的两个不断相加就可以了。
【欧阳韵妍，2021年秋】这道题有两个难点：（1）如何用 greedy 理解题目：一开始能想到剪绳子就相当于拼绳子，但是没有想明白为什么大家在群里说“每次都将最小的两个拼起来”就能达到最小开销，看了吴轩宇同学的解题思路后豁然开朗，“一共需要的步数是一定的（n-1）【这句话是我理解为什么这道题是greedy 的关键】, 但只要我们每次控制开销最少，就达到了局部的贪婪”，感叹一句：greedy 题果然是想到就简单想不到就难。感谢吴轩宇同学提供的解题思路和两个学习网站，我收益匪浅。（2）为什么这道题要用 heapq：齐思远同学的理解对我启发很大“heapq 是一个处理快一点的数据类型”，所以 heapq 只是用来简化寻找最短绳子的过程的而已。把上面两个难点想清楚后，再花点时间看看 heapq 的函数（用吴同学提供的链接https://docs.python.org/zh-cn/3/library/heapq.html）就可以写出代码了。
【陈思同，2021年秋】把切绳子反着想成组合绳子碎片；每次组合长度最短的两段即可，其实很简单。

为了练习heap数据结构，修改了测试点时间限制。下面这段代码是超时的（每次循环从数组头删两次元素）。

python

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
cost = 0
while len(a) > 1:
    cost += a[0]+a[1]
    a.append(a[0]+a[1])
    del a[0]
    del a[0]
    a.sort()
print(cost)

【黄章毅，2021年秋】感觉这题有递归和greedy 的一个结合吧，从相反的方向去思考拼绳子，只要我们将从n条绳子变成n-1 条绳子的开销最少，那么最终的开销就会最少。并且还有个感觉，就是无序的元素很容易通过一定的排序处理来实现greedy，总之还要多尝试，万一哪条路径就是正确的greedy 呢。

python

import bisect
n,ans=int(input()),0
l=sorted([int(i) for i in input().split()])
while len(l)!=1:
    t=l.pop(0)+l.pop(0)
    bisect.insort(l,t)
    ans+=t
print(ans)

M18164: 剪绳子 ​

M18164: 剪绳子