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

难度: Hard

你有 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⁵
1 <= batteries[i] <= 10⁹

Submission

运行时间: 100 ms

内存: 29.4 MB

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        batteries.sort(reverse=True)
        s=sum(batteries)
        for x in batteries:
            if x<=s//n: return s//n
            s -= x
            n -= 1

Explain

此题解采用贪心的方法来分配电池资源，确保所有电脑尽可能长时间运行。首先，将电池数组从大到小排序，以优先使用容量大的电池。在遍历处理过程中，计算当前所有电池的总能量s，并尝试均匀分配到n台电脑上。如果当前最大的电池容量x小于或等于平均每台电脑分到的电量s/n，则此时的s/n就是结果，因为这意味着即使最大电池只能支持到s/n分钟，其他电池的容量也足以支持到这个时间。如果不是，则将这个电池的容量从总能量中减去，并减少电脑的数量，继续尝试下一个电池。

时间复杂度: O(m log m)

空间复杂度: O(1)

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        batteries.sort(reverse=True)  # 将电池按容量从大到小排序
        s = sum(batteries)  # 计算所有电池的总容量
        for x in batteries:  # 遍历每个电池
            if x <= s // n:  # 如果当前电池的容量小于等于平均分配到每台电脑的容量
                return s // n  # 返回这个平均值
            s -= x  # 从总容量中减去当前电池的容量
            n -= 1  # 减少需要供电的电脑数量

Explore

此题解中使用的排序和逐个检查电池的方法在效率上主要受到排序算法的影响。通常的排序算法，如快速排序和归并排序，都具有O(n log n)的时间复杂度，这在大多数情况下是可接受的。但对于非常大的输入数组，排序步骤仍然可能成为性能瓶颈。尽管如此，基于当前题解的逻辑，排序是必须的，因为需要从最大容量电池开始逐个检查。然而，如果可以接受近似解，可以考虑使用更加高效的算法，如基于采样的方法或者使用优先队列（堆）来动态获取当前最大的电池，从而避免完整排序。

题解中未明确指出使用的具体排序算法，但Python的内置排序方法（如使用list的sort()方法）通常基于Timsort算法，这是一种结合了归并排序和插入排序的算法，其平均和最坏情况时间复杂度均为O(n log n)。选择最合适的排序算法时，应考虑数据的特性：例如，如果数据已部分排序，Timsort将表现得非常好。对于完全随机或特别大的数据集，可以考虑使用快速排序或归并排序。如果对稳定性有需求，归并排序是更好的选择。

在算法中，通过将电池数组从大到小排序，确保每次减少的都是当前最大的电池。这种方法有助于保持每一步操作中各电脑平均可使用的最大电量，因为如果一个较大的电池不能均匀分配给所有电脑，较小的电池自然也不可能。这种方式避免了减少容量较小的电池导致的不准确情况。因此，只要排序步骤正确执行，就不会出现因选取错误电池而导致结果不准确的情况。