leetcode 410. Split Array Largest Sum 最小化最大数 + 一个很棒的二分搜索BinarySearch的做法 + 真心很棒-蒲公英云

leetcode 410. Split Array Largest Sum 最小化最大数 + 一个很棒的二分搜索BinarySearch的做法 + 真心很棒

た入场券 2022-06-04 08:12 148阅读 0赞

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

最笨的方法就是暴力求解，但是肯定会超时，后来在网上看了一个二分搜索的做法，想法十分新奇（至少对于我是这样的），收获很大。

分析如下：
如果m和数组nums的个数相等，那么每个数组都是一个子数组，所以返回nums中最大的数字即可，如果m为1，那么整个nums数组就是一个子数组，返回nums所有数字之和，所以对于其他有效的m值，返回的值必定在上面两个值之间，所以我们可以用二分搜索法来做。

我们用一个例子来分析，nums = [1, 2, 3, 4, 5], m = 3，我们将left设为数组中的最大值5，right设为数字之和15，然后我们算出中间数为10，我们接下来要做的是找出和最大且小于等于10的子数组的个数，[1, 2, 3, 4], [5]，可以看到我们无法分为3组，说明mid偏大，所以我们让right=mid，然后我们再次进行二分查找哦啊，算出mid=7，再次找出和最大且小于等于7的子数组的个数，[1,2,3], [4], [5]，我们成功的找出了三组，说明mid还可以进一步降低，我们让right=mid，然后我们再次进行二分查找哦啊，算出mid=6，再次找出和最大且小于等于6的子数组的个数，[1,2,3], [4], [5]，我们成功的找出了三组，我们尝试着继续降低mid，我们让right=mid，然后我们再次进行二分查找哦啊，算出mid=5，再次找出和最大且小于等于5的子数组的个数，[1,2], [3], [4], [5]，发现有4组，此时我们的mid太小了，应该增大mid，我们让left=mid+1，此时left=6，right=5，循环退出了，我们返回left即可。

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
using namespace std;
class Solution 
{
public:
    bool search(vector<int> num, int cut, int target)
    {
        int sum = 0;
        for (int i=0;i<num.size();i++)
        {
            sum += num[i];
            if (sum > target)
            {
                sum = num[i];
                cut--;
                if (cut < 0)
                    return false;
            }
        }
        return true;
    }
    int splitArray(vector<int>& nums, int m) 
    {
        long long right = 0,left = 0;
        for (int a : nums)
        {
            right += a;
            left = max(left, (long long)a);
        }
        while (left < right)
        {
            int mid = (right - left) / 2 + left;
            if (search(nums, m-1,mid))
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
};