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 <= 1000
0 <= nums[i] <= 106
1 <= 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;
}
};