2018 Bytedance AI Camp 编程题2: Split Array Largest Sum

分割分数的最小值

题目描述：

给n个正整数a1, a2, a3, ... ... an，将n个数顺序排成一列后分割成m段，每一段的分数被记为这段内所有数的和，该次分割的分数则被记为m段分数的最大值。问所有的分割方案中分割分数的最小值是多少？

其实本题，就是LeetCode的 410. Split Array Largest Sum。

问题分析：二分查找（Binary Search）

1、所给的数子都是正整数（很重要）。

2、让求的解可以事先确定其的范围[sum(nums) / m，sum(nums)]：

     A: 最优解一定不小于sum(nums) / m，这个很好证明（前提，都是非负数），一个序列nums 被分割m段，如果有一个段小于sum(nums) / m，那么其他子段一定有一个大于平均值数，所以此次分割的分数最小一定是sum(nums) / m。

    B: 其次是，最优解一定不大于sum(nums)，这个很好理解，因为无论它如何分割，子段的最大值不会超过这个序列的总和。

3、由2可知，我们已经知道解的范围，现在只要枚举这些值，选择最优解即可。所以可以使用二分查找，以确定那个值是最优解。

例如：

nums, m = [1, 4, 2, 3, 5], 3

最优解的可能值

	sum(nums) / m										sum(nums)
枚举可能值	5	6	7	8	9	10	11	12	13	14	15

Python实现：

# Bytedance AI Camp 2018 -编程题2-(北京时间)05月26日 09时30分-05月26日 12时00分
# 解题思路  二分查找（Binary Search）
# 将数组nums拆分成m个子数组，每个子数组的和的范围在 [sum(nums) / m，sum(nums)]内
# 又因为数组nums中只包含非负整数，因此可以通过二分法在上下界内搜索最优解。
# 时间复杂度O(n * log m)，其中n是数组nums的长度，m为数组nums的和（准确的说应该是sum(nums)-sum(nums)/m）
# @Time   :2018/5/27
# @Author :LiuYinxing


class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        size = len(nums)
        high = sum(nums)  # 确定上界
        low = high // m  # 确定下界 （下取整）
        while low <= high:
            mid = (low + high) // 2  # （下取整）
            n = m
            cnt = 0
            valid = True
            for x in range(size):
                if nums[x] > mid:  # 如果发现数列里面有一个大于目标解的，说明真正的解在右区间，即继续搜索右区间
                    valid = False
                    break
                if cnt + nums[x] > mid:  # 进行一次分割， 并初始化 n, cnt
                    n -= 1
                    cnt = 0
                cnt += nums[x]  # 统计每次分割的小区间的和，
                if n == 0:  # n == 0 说明划分的段数超过了 m，说明真正的解在右区间，即继续搜索右区间
                    valid = False
                    break
            if valid:  # 确定下一个要搜索的区间范围
                high = mid - 1  # valid == True 说明最优解还可以再小，即在左区间里面
            else:
                low = mid + 1
        return low


if __name__ == '__main__':
    solu = Solution()
    nums, m = [1, 4, 2, 3, 5], 3
    print(solu.splitArray(nums, m))

发现问题，请留言指正哦