每周一课：L14 Binary search algorithm

0.png

P14.2 MinMaxDivision
Divide array A into K blocks and minimize the largest sum of any block.

• P14.2 最大最小拆分
  将数组A分成K块，使得所有块的和值的最大值最小

给定整数K，M和一个由N个整数组成的非空数组A。数组的每个元素都不大于M。将这个数组分成K个连续的块。块的大小是0到N之间的任何整数。数组的每个元素都应该属于某个块。

从X到Y的块之和等于A[X] + A[X + 1] + ... + A[Y]。空块的和等于0。大和指的是是所有块的和值中的最大值。

例如，给定整数K = 3, M = 5 和数组A：

A[0] = 2，A[1] = 1，A[2] = 5，A[3] = 1，A[4] = 2，A[5] = 2，A[6] = 2

可以将数组划分为以下块：

• [2, 1, 5, 1, 2, 2, 2], [], []：最大和值为15;
• [2]、[1、5、1、2]、[2、2]：最大和值为9；
• [2，1，5]，[]，[1，2，2，2]：最大和值为8；
• [2，1]，[5，1]，[2，2，2]：最大和值为6；

目的是得到最小的最大和值。在上面的例子中，6是最小的大和。

编写函数：

def solution(K, M, A)

给定整数K，M和由N个整数组成的非空数组A，则返回最小的大和。

例如，针对上面的例子，函数应该返回6。

假定：

1. N和K是区间[1，100000]中的整数；
2. M是区间[0，10000]中的整数；
3. 数组A的每个元素都是区间[0，M]中的整数；

• 解题思路

最终的大和值肯定不会小于数组A的最大值，也不会大于数组A的和值。按照二分查找的算法，预设一个值，然后计算按照此值，需要将数组A变为几个块。如果块数多于K，说明预设的值偏小，需要增大。如果块数小于K，说明预设的值偏大，需要减小预设值。这种思想就和二分查找一样。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 14：Binary search algorithm
# P 14.2 MinMaxDivision


def get_blocks(A, compare_num):
    """
    如果最大数值为compare_num，整个A可以分为多少块
    :param A: 正整数数组
    :param compare_num: 目标数值
    :return: 块数
    """
    blocks = 0
    num_sum = 0
    for i in A:
        num_sum += i
        if num_sum > compare_num: # 大于目标数值
            num_sum = i
            blocks += 1  # 块数需要加1
    return blocks + 1   # 最后这几个数算作一个块


def solution(K, M, A):
    """
    将数组A分为连续的K块，使得所有块的和的最大值最小
    :param K: 块的个数
    :param M: 数组A中元素的最大值不大于此数
    :param A: 正整数数组
    :return: 大和的最小值
    """
    sum_num = sum(A)
    if K == 1:
        return sum_num
    else:
        max_num = max(A)
        if K >= len(A):
            return max_num
        else:
            while max_num <= sum_num:  # 因为和值的最小值为max_num，最大值为sum_num，采用二分法查找
                middle = int((sum_num - max_num) / 2) + max_num
                blocks_count = get_blocks(A, middle)
                if K >= blocks_count:  # 需要分的块数再多点，因此减小middle
                    sum_num = middle - 1
                else:  # 需要分的块数再少点，因此增大middle
                    max_num = middle + 1
            return max_num

• 结果

image

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

image image