Last Updated on 2022-03-31 by Clay
題目
Given an array nums 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.
Example 1:
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.
Example 2:
Input: nums = [1,2,3,4,5], m = 2 Output: 9
Example 3:
Input: nums = [1,4,4], m = 3 Output: 4
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= m <= min(50, nums.length)
題目輸入一個非排序後的純數值陣列 nums，以及可分割的數量 m。我們要做的就是將陣列分割成 m 個子陣列，並讓子陣列中加總最大的值保證在所有分割可能中是最小的。
解題思路
（由於接種疫苗因素，本日無更詳細的解法解釋）
二元搜索解法
我有看到討論區有 DP 的解法… 但我實在沒心力去解出來，只有想出用二元搜索的方式來解題。
二元搜索的邊界中，最小的左值應為陣列中的最大值，因為每單一值為一個子陣列通常是最小的切法（雖然根據題目中給予的 m 會導致我們很難做到這一點）。
最大的右值應為整個陣列加總，因為整個陣列就是一個子陣列就會是最糟的情況。
決定好邊界值後，接下來就是進行經典二元搜索了。二元搜索中我額外建立了一個函式 canSplit() 來判斷這樣是否可切成 m 個子陣列。
當子陣列中的加總值大於當前我們判斷的中間值時，即需要切割出新的子陣列 —— 因為我們需要最大的加總值不要超過當前判斷的中間值。
而一但需要切割的次數多了，超過題目設定的 m 個子陣列時，則代表當前設定的最大值太小了，導致需要切太多的子陣列，所以這時我們就需要提高我們的最小的邊界值左值，來讓我們可以考慮更大的中間值（子陣列中加總的最大值）。
而一但確定當前的中間值可以切割，則我們就可以更貪婪地將最大邊界值右值縮小為中間值減一，來找到更小的最大值。
有點繞口，頭腦開始昏昏沉沉的了，還是直接看程式碼吧！
二元搜索法 C++ 範例程式碼
class Solution {
public:
bool canSplit(vector<int>& nums, int m, int curr) {
// Init
int count = 1;
int sum = 0;
// Try to split
for (int n: nums) {
if (sum + n <= curr) {
sum += n;
}
else {
sum = n;
++count;
if (count > m) return false;
}
}
return true;
}
int splitArray(vector<int>& nums, int m) {
// Init
int left = 0;
int right = 0;
// Determine the left and right boundary
for (auto& n: nums) {
right += n;
left = max(left, n);
}
// Assign the worse case to initialize ans
int ans = right;
// Binary search
while (left <= right) {
int mid = left + (right-left) / 2;
// If the mid number can split, try to find the more little sum
if (canSplit(nums, m, mid)) {
ans = min(ans, mid);
right = mid - 1;
}
// If mid number cannot split, try to find the larger sum
else {
left = mid + 1;
}
}
return ans;
}
};