算法实战：牛客23458题数组分割最小化最大和的二分查找与贪心解法

8个月前 (07-04)牛客题解262

一、问题背景与理解

牛客23458题要求将一个数组分割成m个子数组，使得这些子数组各自和的最大值最小。这是一个典型的算法优化问题，结合了二分查找和贪心算法的思想。

二、完整代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

bool canSplit(const vector<int>& nums, int m, long long maxSum) {
    int count = 1;
    long long currentSum = 0;
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            currentSum = num;
            count++;
            if (count > m) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

int minMaxPartition(vector<int>& nums, int m) {
    long long left = *max_element(nums.begin(), nums.end());
    long long right = accumulate(nums.begin(), nums.end(), 0LL);
    
    while (left < right) {
        long long mid = left + (right - left) / 2;
        if (canSplit(nums, m, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    cout << minMaxPartition(nums, m) << endl;
    return 0;
}