深海潜艇探险

这道题是贪心策略，先穿过能净增能的区域，再穿过净亏能的区域。净增能的区域先走能量要求门槛低的，净亏能区域要先走（亏+补）总和最大的

亏损区域证明

要严谨证明亏损区域需按 ai​+bi​ 降序排序，我们从两个亏损区域的顺序优化入手，结合交换论证推广到多个区域。

一、定义与前提

设亏损区域满足 bi​<ai​（穿越后能量净减少）。对于任意两个亏损区域：

• X(a1​,b1​)：b1​<a1​，C1​=a1​+b1​（记为 X 的 “特征值”）。
• Y(a2​,b2​)：b2​<a2​，C2​=a2​+b2​（记为 Y 的 “特征值”）。

我们需要比较先 X 后 Y 和先 Y 后 X 两种顺序的最小初始能量要求，证明：当 C1​≥C2​ 时，先 X 后 Y 所需的初始能量更小（更优）。

二、两种顺序的能量条件推导

设初始能量为 E，S=a1​+a2​（两区域消耗的总能量）。

1. 先 X 后 Y 的条件

• 穿越 X：必须 E>a1​（能量足够支付 X 的门槛）。
• 穿越 X 后能量：E1​=E−a1​+b1​。
• 穿越 Y：必须 E1​>a2​ → 代入得 E>a1​+a2​−b1​=S−b1​。

因此，先 X 后 Y 的最小初始能量为：EXY​=max(a1​,S−b1​)

2. 先 Y 后 X 的条件

• 穿越 Y：必须 E>a2​。
• 穿越 Y 后能量：E2​=E−a2​+b2​。
• 穿越 X：必须 E2​>a1​ → 代入得 E>a1​+a2​−b2​=S−b2​。

因此，先 Y 后 X 的最小初始能量为：EYX​=max(a2​,S−b2​)

三、比较 EXY​ 和 EYX​

由于 X,Y 是亏损区域（b1​<a1​,b2​<a2​），可推导：S−b1​=a1​+a2​−b1​=a2​+(a1​−b1​)>a2​(因 a1​−b1​>0)S−b2​=a1​+a2​−b2​=a1​+(a2​−b2​)>a1​(因 a2​−b2​>0)

因此，EXY​ 和 EYX​ 可简化为：EXY​=S−b1​,EYX​=S−b2​

（若 a1​>S−b1​，则 EXY​=a1​，但结合 S−b1​>a2​ 和 C1​≥C2​，可进一步证明此情况不影响结论，此处简化核心逻辑。）

四、关键等价关系

特征值 C1​=a1​+b1​≥C2​=a2​+b2​ → 移项得：b1​−b2​≥a2​−a1​

代入 EXY​=S−b1​ 和 EYX​=S−b2​：EXY​=S−b1​≤S−b2​=EYX​

结论：当 C1​≥C2​（X 的特征值更大）时，先 X 后 Y 所需的初始能量更小，顺序更优。

数据m溢出问题

题目中n是最大10^5，每个区域能量盈利最大10^5，那么最终m可能累加到10^10，也就是100亿，但是int类型最大范围是21亿多，会溢出

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    /**
     * 求n个区域是否可以全部通过
     * @param n 危险区域数量
     * @param m 初始能量
     * @param power n*2的数组，0列是消耗的能量、1列是获得的能量
     * @return
     */
    private static boolean isTransfored(int n, long m, int[][] power) {
        //1.两个列表，一个存储收益区域，一个存储亏损区域
        List<int[]> profit = new ArrayList<>();
        List<int[]> lose = new ArrayList<>();
        //2.遍历power进行区域收集
        for (int[] ints : power) {
            if (ints[1] >= ints[0]) {
                profit.add(ints);
            } else {
                lose.add(ints);
            }
        }
        //3.对收益区域进行排序，按照收益门槛升序排序，亏损区域按照亏损+补能降序排序
        profit.sort((a, b) -> a[0] - b[0]);
        lose.sort((a, b) -> b[0] + b[1] - a[0] - a[1]);
        //4.先遍历收益区域进行能量累加
        for (int[] ints : profit) {
            if (m <= ints[0]) {
                return false;
            }
            m += ints[1] - ints[0];
        }
        //5.再遍历亏损区域进行扣减
        for (int[] ints : lose) {
            if (m <= ints[0]) {
                return false;
            }
            m += ints[1] - ints[0];
        }
        //6.到这里说明都能通过返回true
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            long m = scanner.nextLong();
            int[][] power = new int[n][2];
            for (int i = 0; i < n; i++) {
                power[i][0] = scanner.nextInt();
                power[i][1] = scanner.nextInt();
            }
            System.out.println(isTransfored(n, m, power) ? "Yes" : "No");
        }
        scanner.close();
    }
}

分布式计算任务调度

这道题是 非常经典 的算法题，其核心模型对应 LeetCode 上的 410. 分割数组的最大值（Hard 难度），属于 “最小化最大段和” 类问题的标杆题目，在面试、算法竞赛中高频出现。

为什么它是经典题？

1. 问题模型的普适性

这道题的约束（连续分段、固定段数上限、最小化最大段和）是很多实际场景的抽象：

• 除了 “分布式任务调度”，还可对应：
  • 书籍分配：将 N 本书分给 M 个学生，每人只能拿连续的书，求每人最少要拿的最大页数。
  • 磁盘分区：将连续的磁盘空间分成 M 个分区，使最大分区容量最小。
  • 生产线拆分：将连续的生产工序分成 M 个环节，使最长环节的耗时最小。
• 本质是 “资源分配” 类问题的核心抽象，解决它能举一反三应对一类场景。

2. 解法的典型性

这道题的最优解法（二分查找）是 “最小化最大值”“最大化最小值” 类问题的 标准解法，属于必须掌握的高频解题模板：

• 核心思路 “二分查找 + 贪心验证” 的组合，适用于所有 “满足某约束条件下，优化极值” 的问题（比如 LeetCode 1011. 在 D 天内送达包裹的能力、LeetCode 875. 爱吃香蕉的珂珂）。
• 很多新手会本能想到动态规划（DP）解法，但二分查找的时间复杂度更优（O(N log S) vs O(N²M)），尤其适合 N 较大的场景（本题 N≤1000，DP 也能过，但 N=1e4 时 DP 会超时）。

3. 考点的全面性

它同时考察两个核心能力：

• 二分查找的边界设计：如何确定左边界（单个元素最大值）和右边界（数组总和），以及如何通过 “贪心验证” 收缩区间。
• 贪心算法的应用：验证某一 “最大段和” 是否可行时，用 “能加就加，加不下就新开一段” 的贪心策略，高效判断是否能在 M 段内完成分割。

经典变体与延伸

掌握这道题后，同类变体都能快速解决：

• 变体 1：M 是 “最小段数”，求 “最大化最小段和”（比如将数组分成至少 M 段，使最小段和最大）—— 同样用二分查找，调整验证逻辑即可。
• 变体 2：任务有依赖关系（非连续，但本题约束连续，是简化版）。
• 变体 3：节点有负载上限，求最少需要多少个节点（本质是二分查找的逆问题）。

农田最大产出评估

和leetcode84题求最大柱状图的面积一摸一样，利用单调栈求解“凸起部分”的最大面积

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] outPut = new int[n + 2];
        for (int i = 0; i < n; i++) {
            outPut[i + 1] = scanner.nextInt();
        }
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < outPut.length; i++) {
            while (outPut[stack.peek()] > outPut[i]) {
                int height = outPut[stack.pop()];
                int width = i - stack.peek() - 1;
                result = Math.max(result, height * width);
            }
            stack.push(i);
        }
        System.out.println(result);
        scanner.close();
    }
}