题目

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑运行 batteries[i] 分钟。你想使用这些电池让全部 n 台电脑同时运行。

一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的最长分钟数。

示例 1：

输入：n = 2, batteries = [3,3,3] 输出：4 解释：一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。 2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。

示例 2：

输入：n = 2, batteries = [1,1,1,1] 输出：2 解释：一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。 1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。

提示：

1 <= n <= batteries.length <= 10^5
1 <= batteries[i] <= 10^9

解题思路

先假设：

我想让 n 台电脑 同时运行 t 分钟，能不能做到？

如果我们能写一个函数 check(t)，告诉我们：

check(t) == true：电池总量 + 调度方式，能让所有电脑都撑过 t 分钟
check(t) == false：无论怎么换电池，都撑不到 t 分钟

那么这道题就变成：

在所有 t 中，找最大的那个满足 check(t) == true 的 t。

而且注意到：如果某个时间 t 能撑住，那么任何 t' < t 肯定也能撑住 —— 你让电脑少跑点，更不紧张嘛。也就是说：check(t) 关于 t 是单调的：`

这种“前面都是 true，后面都是 false”的典型单调结构，最适合用二分查找。

假设我们要让每一台电脑都至少运行 t 分钟，没有中途挂掉。

每块电池 batteries[i] 最多只能贡献它自己的电量那样多，但是我们可以随时把电池拔下、插到别的电脑上，互相轮着用。

对于一个给定的 t，一块电池最多能为“所有电脑合计”贡献 min(batteries[i], t) 分钟。

原因是：

如果这块电池容量 b_i >= t：它最多能在整个时间轴上被某几台电脑轮流用，总共用了 t 分钟（因为电脑只需要跑 t 分钟，超过了也没意义） → 总贡献为 t
如果这块电池容量 b_i < t：它就会被某台电脑用到耗尽，总贡献就是 b_i → 总贡献为 b_i

所以，对给定 t，所有电池能贡献的总时间是：

$$\mathrm{total}(t)=\sum_i\min(b_i,t)$$

而我们需要的是：

n 台电脑，每台连续运行 t 分钟 也就是：总需求时间 = n * t

只要总供给时间 ≥ 总需求时间，就一定可以通过合理调度（不停地换电池）让电脑坚持住。

所以判断条件非常简单：

$$\text{如果 }\sum_i\min(b_i,t)\geq n\cdot t\text{ 则 t 可行;否则不可行。}$$

这就是 check(t) 的逻辑。

我们要二分的 t 要有个范围 [left, right]。

下界 left

最小运行时间肯定是 0 分钟 → 一定可以做到 → 所以 left = 0 是安全的起点。

上界 right

总电量是：

$$\mathrm{sum}=\sum_ib_i$$

假设我们不考虑调度细节，只考虑「平均能撑多久」：

所有电脑一共要跑 t 分钟，消耗总电量是 n * t 而我们手上的总电量只有 sum

显然有一个硬约束：

$$n\cdot t\leq\mathrm{sum}\Rightarrow t\leq\left\lfloor\frac{\mathrm{sum}}{n}\right\rfloor$$

也就是说：

最大能撑的时间一定不超过 sum / n

所以我们可以把右边界设成：

right = sum / int64(n)

这个 right 自己可能可行，也可能不可行，但一定是一个安全上界。

我们要找的是「最大的 t，使得 check(t) == true」，这是典型的：

闭区间找最大满足条件值

标准写法：

l, r := 0, right
for l < r {
    mid := l + (r - l + 1) / 2  // 上取整
    if check(mid) == true {
        l = mid                 // mid 可行，往右边找更大的
    } else {
        r = mid - 1             // mid 不可行，往左缩
    }
}
return l    // l == r，为最大可行 t

具体代码

func maxRunTime(n int, batteries []int) int64 {

    sum := int64(0)
    for _, i := range batteries {
        sum += int64(i)
    }

    k := sum / int64(n)

    left := int64(0)
    right := k

    for left < right {

        mid := left + (right - left + 1) / 2

        total := int64(0)
        need := int64(n) * mid
        for _, i := range batteries {
            total += min(mid, int64(i))
        }

        if total >= need {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

2141. 同时运行 N 台电脑的最长时间

beautifulremi

题目

解题思路

具体代码