首页<<

如何解决最大值最小问题？

前言

最大值最小问题是算法竞赛中的经典题型，其核心思想是通过二分查找来寻找满足条件的最优解。这类问题通常具有单调性，即当某个值可行时，比它更大的值也必定可行。掌握这类问题的解题思路，对于提高算法思维能力非常有帮助。

问题描述

让我们从一个具体的例子来理解最大值最小问题：

火车装载问题：有n个包裹需要装载到m节车厢中，每个包裹有一定的重量，每节车厢有最大载重限制。我们需要找到最小的载重限制，使得所有包裹都能被装载。

这就是典型的"最大值最小"问题 - 我们要最小化所有车厢中的最大载重。

解题思路

1. 问题分析

对于这类问题，我们可以思考：

• 如果载重限制为x时可以装下所有包裹，那么载重限制为x+1, x+2...也一定可以
• 这种单调性让我们可以使用二分查找来寻找最小的可行解

2. 二分查找的边界

• 左边界：至少要能装下最重的包裹，所以是max(所有包裹重量)
• 右边界：最坏情况下用一节车厢装所有包裹，所以是sum(所有包裹重量)

3. 检查函数

关键在于实现一个检查函数check(capacity)，判断在给定载重限制下是否能装下所有包裹：

const check = (capacity) => {
    let carriagesNeeded = 1;  // 至少需要一节车厢
    let currentSum = 0;       // 当前车厢的载重
    
    for (let i = 0; i < n; i++) {
        if (p[i] > capacity) {
            // 单个包裹超过载重限制，无法装载
            return false;
        }
        if (currentSum + p[i] <= capacity) {
            // 当前车厢还能装下这个包裹
            currentSum += p[i];
        } else {
            // 需要新的车厢
            carriagesNeeded++;
            currentSum = p[i];
        }
    }
    
    return carriagesNeeded <= m;
};

完整实现

function solve(input) {
    const lines = input.trim().split('\n');
    const [n, m] = lines[0].split(' ').map(Number);
    const p = lines[1].split(' ').map(Number);

    const check = (capacity) => {
        let carriagesNeeded = 1;
        let currentSum = 0;
        for (let i = 0; i < n; i++) {
            if (p[i] > capacity) {
                return false;
            }
            if (currentSum + p[i] <= capacity) {
                currentSum += p[i];
            } else {
                carriagesNeeded++;
                currentSum = p[i];
            }
        }
        return carriagesNeeded <= m;
    };

    // 确定二分查找的边界
    let left = 0;
    for (const size of p) {
        left = Math.max(left, size);
    }
    
    let right = 0;
    for (const size of p) {
        right += size;
    }
    
    let ans = right;

    // 二分查找最小的可行载重限制
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            ans = mid;
            right = mid - 1;  // 尝试更小的值
        } else {
            left = mid + 1;   // 当前值太小，尝试更大的值
        }
    }

    console.log(ans);
}

算法复杂度分析

• 时间复杂度：O(n * log(sum - max))
  • 二分查找的次数为O(log(sum - max))
  • 每次检查需要O(n)时间遍历所有包裹
• 空间复杂度：O(1)，只使用了常数级别的额外空间

测试用例分析

示例1

输入：3 3
      1 6 4
输出：6

分析：有3个包裹（重量分别为1,6,4），3节车厢。最优方案是每节车厢装一个包裹，所以最大载重为6。

示例2

输入：5 2  
      7 2 5 10 8
输出：18

分析：有5个包裹，2节车厢。一种方案是第一节车厢装[7,2,5]，第二节车厢装[10,8]，最大载重为18。

类似问题的拓展

最大值最小问题在很多场景中都有应用：

1. 任务调度：将n个任务分配给m个处理器，最小化最大完成时间
2. 网络带宽：在网络中找到最大流的最小瓶颈
3. 资源分配：将资源分配给不同部门，最小化最大分配量

解题模板：

function binarySearchMinMax(arr, groups) {
    let left = Math.max(...arr);
    let right = arr.reduce((sum, val) => sum + val, 0);
    let result = right;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canAchieve(arr, groups, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

总结

最大值最小问题的关键在于：

1. 识别单调性：找到问题中的单调递增或递减关系
2. 确定边界：合理设置二分查找的左右边界
3. 实现检查函数：高效判断某个值是否可行
4. 二分查找：在可行解中找到最优解

掌握了这个思路，我们就能解决一大类优化问题。在实际编程中，二分查找不仅仅用于在有序数组中查找元素，更是解决最优化问题的有力工具！

致谢

• 感谢算法竞赛社区的宝贵资源和讨论

预告

• 动态规划入门指南
• 图论算法详解
• 数据结构优化技巧

关于

作者：bigonion
邮箱：bigonion@bigonion.cn
NameSpace: 大聪花的家
Origin: 大聪花的博客
Powered by markdown 在线

声明：未经本人同意,禁止转载、搬运、抄袭！