Codility每周一课大数据,机器学习,人工智能数据结构和算法分析

每周一课:L16 Greedy algorithms(16.2)

2019-02-21  本文已影响0人  AiFany
0.png
P16.2 TieRopes

Tie adjacent ropes to achieve the maximum number of ropes of length >= 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
绳索如下图所示:

image

通过以下操作:

  1. 绳索编号为1和2的系在一起,产生了长度为A[1]+A[2]=5的新绳索;
  2. 绳索编号为4、5、6的系在一起,产生了长度为A[4]+A[5]+A[6]=5的新绳索。
image

此时,有3根长度不小于K=4的绳索(蓝框中显示)。不管如何操作,也不可能产生4根满足长度条件的绳索。

编写函数:

def solution(K, A)

给定整数K和N个整数的非空数组A,则返回可以得到的长度不小于K的绳索数的最大值。例如,针对上面的例子,函数应该返回3。

假定:

  1. N是区间[1,100,000]内的整数;
  2. K是区间[1,1,000,000,000]内的整数;
  3. 数组A的每个元素都是区间[1,1,000,000,000]内的整数;

利用贪婪算法,遍历数组A,如果当前元素的值不小于K,则此绳索不需要系,最终的绳索数直接加1。如果小于K,则系上,直到系上之后的新的绳索的长度不小于K,此时新的绳索满足条件,最终的绳索数加1。然后重新开始下一次的判断。

# -*- 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
image

点击获得更多编程练习题。欢迎Follow,感谢Star!!! 扫描关注微信公众号pythonfan,获取更多。

image image
上一篇 下一篇

猜你喜欢

热点阅读