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

### 题目地址(2141. 同时运行 N 台电脑的最长时间 - 力扣（LeetCode）)

<https://leetcode.cn/problems/maximum-running-time-of-n-computers/?utm\\_source=LCUS\\&utm\\_medium=ip\\_redirect\\&utm\\_campaign=transfer2china>

### 题目描述

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

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

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

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

&#x20;

**示例 1：**

![](https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png)

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

**示例 2：**

![](https://assets.leetcode.com/uploads/2022/01/06/example2.png)

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

&#x20;

**提示：**

* `1 <= n <= batteries.length <= 105`
* `1 <= batteries[i] <= 109`

### 前置知识

* 二分

### 公司

* 暂无

### 思路

我们可以将时间作为横坐标，电脑作为纵坐标，直观地用图来描述电池的分配情况。这位博主画了一个图，很直观，我直接借用了

![](https://p.ipic.vip/oup1k5.png)

题目给的例子 n = 2, batteries = \[3,3,3] 很有启发。如果先将电池 0 和 电池 1 给两个电脑，然后剩下一个电池不能同时给两个电脑分配，因此这种分配不行。

那么具体如何分配呢？ 我们其实不用关心，因为题目不需要给出具体的分配方案。而是给出具体的使用时间即可。

需要注意的是，只要电量够，那么一定可以找到一种分配方法。

电量够指的是：

* 对于一个电池，如果其电量大于 t，那么只能用 t。因为一个电池同时只能给一个电脑供电。
* 对于一个电池，如果其电量小于等于 t，那么我们可以全部用掉。

合起来就是：sum(\[min(t, battery) for battery in batteries])

如果合起来大于等于需要的电量（这里是 n \* t），那么就一定可以有一种分配方案，使得能够运行 t 分钟。

如何证明一定可以找到这种办法呢？

对于 \[3, 3, 3] n = 2 这个例子，我们可以调整最后 1 分钟的电池分配情况使得不重叠（不重叠指的是不存在一个电池需要同时给两个电脑供电的情况）。

那么如何调整？实际上只要任意和前面电池的 1 分钟进行交换，两个不重叠就好。

可以证明如果电池电量小于总运行时间 t，我们一定可以进行交换使得不重叠。如果大于 t，由于我们最多只能用到 t，因此 t 的部分能够交换不重叠， 而超过 t 的部分根本用不到，不用考虑。

大家也可以反着想。 **如果不存在**一种交换方式使得不重叠。那么说明至少有一个电池的运行时间大于 t，这与题目矛盾。（因为运行 t 时间， 电池不同给多个电脑供电，也就是说电池最多消耗 t 的电量）大家可以结合前面的图来进行理解。

### 关键点

* 证明总的可用电池大于等于总的分钟数是充要条件

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        def can(k):
            return sum([min(k, battery) for battery in batteries]) >= n * k
        l, r = 0, sum(batteries)
        while l <= r:
            mid = (l + r) // 2
            if can(mid):
                l = mid + 1
            else:
                r = mid - 1
        return r

```

**复杂度分析**

令 n 为数组长度，C 为 batteries 数组的 n 项和。

* 时间复杂度：$O(nlogC)$
* 空间复杂度：$O(1)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/h9nm77.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2141.maximum-running-time-of-n-computers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.