每周一课:L16 Greedy algorithms(16.2)
2019-02-21 本文已影响0人
AiFany
![](https://img.haomeiwen.com/i4734220/2de7a6ec3954a308.png)
P16.2 TieRopes
Tie adjacent ropes to achieve the maximum number of ropes of length >= K.
-
P16.2 系绳索
通过系紧相邻的绳索,计算使得绳索长度不小于K的绳索数最多
地板上有N条绳索,编号从0到N-1,其长度在数组A中给出,编号为I(0 ≤ I < N)的绳索的长度为A[I]。
编号相邻(I和I+1为相邻编号)的两条绳索可以系在一起形成新的绳索,而形成的绳索的长度是两条绳索的长度之和,新的绳索同样也可以和相邻的绳索系在一起。对于给定的整数K,目标是计算使得绳索长度不小于K的绳索数的最大值。
例如,考虑K=4和数组A:
A[0]=1,A[1]=2,A[2]=3,A[3]=4,A[4]=1,A[5]=1,A[6]=3
绳索如下图所示:
通过以下操作:
- 绳索编号为1和2的系在一起,产生了长度为A[1]+A[2]=5的新绳索;
- 绳索编号为4、5、6的系在一起,产生了长度为A[4]+A[5]+A[6]=5的新绳索。
此时,有3根长度不小于K=4的绳索(蓝框中显示)。不管如何操作,也不可能产生4根满足长度条件的绳索。
编写函数:
def solution(K, A)
给定整数K和N个整数的非空数组A,则返回可以得到的长度不小于K的绳索数的最大值。例如,针对上面的例子,函数应该返回3。
假定:
- N是区间[1,100,000]内的整数;
- K是区间[1,1,000,000,000]内的整数;
- 数组A的每个元素都是区间[1,1,000,000,000]内的整数;
- 解题思路
利用贪婪算法,遍历数组A,如果当前元素的值不小于K,则此绳索不需要系,最终的绳索数直接加1。如果小于K,则系上,直到系上之后的新的绳索的长度不小于K,此时新的绳索满足条件,最终的绳索数加1。然后重新开始下一次的判断。
- Python3代码
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 16:Greedy algorithms
# P 16.2 TieRopes
def solution(K, A):
"""
通过系住相邻的绳索,使得最终满足长度条件的绳索数最大
时间复杂度:O(N)
:param K: 最终绳索的长度的最小值
:param A: 绳索的长度
:return: 满足条件的绳索数的最大值
"""
count = 0
length = 0
for i in A:
if i >= K:
length = 0
count += 1
else:
length += i
if length >= K:
length = 0
count += 1
return count
- 结果
点击获得更多编程练习题。欢迎Follow,感谢Star!!! 扫描关注微信公众号pythonfan,获取更多。