分割数组

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @param m int整型
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/7a41720ebed04f37bb015febda6a75cb?tpId=196&tqId=40413&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        借鉴kjldvsdhv大神提交
    算法：
        题目要求将数组nums分割成n份，要求子数组累加和最大值尽可能小。
        反向思考：我们以threshold将nums中的元素进行分割，如果恰好分割成m份，说明threshold就是所求解；否则，若分割结果大于m，说明threshold取小了；否则，说明threshold取大了。
        threshold的取值范围：[max(nums), sum(nums)]
        对于threshold的选取，这里我们采用二分查找的方式
    复杂度：
        时间复杂度：O(logD * N), D = sum(nums) - max(nums), N为数组nums的长度
        空间复杂度：O(1)
    """

    def splitMin(self, nums, m):
        def checkSplit(threshold):
            curSum, count = 0, 1 # 初始子数组累加和为0，数组未分割，只有1个区间

            for num in nums:
                curSum += num
                if curSum > threshold: # 找到一个分割点，重置子数组累加和为num，子区间+1
                    count += 1
                    curSum = num

            return count > m

        left, right = max(nums), sum(nums)

        while left < right:
            mid = left + ((right - left) >> 1)

            if checkSplit(mid): # 以子数组和mid进行分割，得到的分割区间大于m，说明left取小了
                left = mid + 1
            else:
                right = mid

        return left

if __name__ == "__main__":
    sol = Solution()

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

    res = sol.splitMin(nums, m)

    print res

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @param m int整型
     * @return int整型
     */
    int splitMin(vector<int>& num, int m) {
        int left = 0, right = 0;
        for (int i = 0; i < num.size(); i++) {
            left = max(left, num[i]);
            right += num[i];
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cnt = 1, sum = 0;
            for (int i = 0; i < num.size(); i++) {
                if (sum + num[i] <= mid) {
                    sum += num[i];
                } else {
                    cnt++;
                    sum = num[i];
                }
            }
            if (cnt <= m) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};