当前位置：首页 > 牛客 > 牛客23458题解析：基于二分查找的动态规划解法与代码实现

牛客23458题解析：基于二分查找的动态规划解法与代码实现

2天前

一、题目解读

牛客23458题要求将给定的整数数组划分为m个连续子数组，使得每个子数组的和不超过某个最大值，且该最大值尽可能小。题目本质是求解“最小化最大值”的优化问题，需要结合二分查找与动态规划思想，找到满足条件的临界值。

二、解题思路

采用经典的“二分答案”策略：首先确定可能的最大值范围（数组元素最大值到元素总和），通过二分查找缩小范围。核心在于设计一个判断函数canSplit()，用于验证当前假设的最大值是否能将数组划分为m个子数组。若可划分则缩小上限，否则扩大下限，最终找到最小可行值。

三、解题步骤解析

1. 边界确定：左边界为数组最大值，右边界为元素总和，确保二分范围有效。

2. 二分查找循环：每次计算中间值mid，调用canSplit()判断是否可行。

3. 可行性判断：通过遍历数组，动态维护当前子数组和，若超过mid则新增子数组计数器，若计数器超过m则说明mid不可行。

4. 结果收敛：循环结束时，left即为满足条件的最小最大值。

四、代码与注释

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

// 判断函数：检查是否能将nums按不超过maxSum划分为m个子数组
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;   // 超过m个，不可行
        } 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;
}