Hard

题目描述

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

一开始，你可以给每台电脑最多插入一个电池。之后，在任何整数时刻，你可以将电池从一台电脑取出并插入另一个电池，次数不限。插入的电池可以是一个全新的电池，也可以是从别的电脑拿出来的电池。假设拿出和插入电池的过程不消耗时间。

注意，电池不能充电。

请你返回你最多能够同时让 n 台电脑运行多少分钟。

示例 1：

输入：n = 2, batteries = [3,3,3]
输出：4
解释：
一开始，将 0 号电池插入第一台电脑，将 1 号电池插入第二台电脑。
2 分钟后，将 1 号电池从第二台电脑拿出，插入 2 号电池。注意 1 号电池还可以运行 1 分钟。
第 3 分钟结尾，0 号电池用完，将它从第一台电脑拿出，插入 1 号电池。
第 4 分钟结尾，1 号电池也用完，第一台电脑无法继续运行。
我们最多能同时让两台电脑运行 4 分钟，所以我们返回 4 。

示例 2：

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

提示：

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

解题思路

这道题的核心思想是二分搜索 + 贪心验证。

思路分析：

对于给定的运行时间 t，我们需要判断是否能让 n 台电脑同时运行 t 分钟。关键观察是：

  • 如果某个电池容量超过 t，那么多余的容量无法被其他电脑使用（因为这个电池在 t 时间内只能为一台电脑服务）
  • 所有容量不超过 t 的电池可以通过不断切换在电脑间共享使用

验证策略：

  1. 将所有容量大于 t 的电池各自分配给一台电脑（这些电池无法共享）
  2. 剩余的电脑需要由容量不超过 t 的电池来供电
  3. 这些小容量电池的总电量必须至少为 剩余电脑数 × t

二分搜索边界：

  • 下界：0
  • 上界：所有电池总电量除以 n（平均分配的理想情况）

由于电池容量可能很大，需要使用 long long 避免溢出。

推荐解法： 二分搜索 + 贪心验证，时间复杂度最优。

代码实现

class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        long long left = 0, right = 0;
        for (int battery : batteries) {
            right += battery;
        }
        right /= n;
        
        while (left < right) {
            long long mid = left + (right - left + 1) / 2;
            if (canRun(n, batteries, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
    
private:
    bool canRun(int n, vector<int>& batteries, long long time) {
        long long sum = 0;
        int usedComputers = 0;
        
        for (int battery : batteries) {
            if (battery >= time) {
                usedComputers++;
            } else {
                sum += battery;
            }
        }
        
        return usedComputers <= n && sum >= (long long)(n - usedComputers) * time;
    }
};

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        def canRun(time):
            sum_small = 0
            used_computers = 0
            
            for battery in batteries:
                if battery >= time:
                    used_computers += 1
                else:
                    sum_small += battery
            
            return used_computers <= n and sum_small >= (n - used_computers) * time
        
        left, right = 0, sum(batteries) // n
        
        while left < right:
            mid = (left + right + 1) // 2
            if canRun(mid):
                left = mid
            else:
                right = mid - 1
        
        return left

public class Solution {
    public long MaxRunTime(int n, int[] batteries) {
        long left = 0, right = 0;
        foreach (int battery in batteries) {
            right += battery;
        }
        right /= n;
        
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (CanRun(n, batteries, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
    
    private bool CanRun(int n, int[] batteries, long time) {
        long sum = 0;
        int usedComputers = 0;
        
        foreach (int battery in batteries) {
            if (battery >= time) {
                usedComputers++;
            } else {
                sum += battery;
            }
        }
        
        return usedComputers <= n && sum >= (long)(n - usedComputers) * time;
    }
}

var maxRunTime = function(n, batteries) {
    const canRun = (time) => {
        let sumSmall = 0;
        let usedComputers = 0;
        
        for (const battery of batteries) {
            if (battery >= time) {
                usedComputers++;
            } else {
                sumSmall += battery;
            }
        }
        
        return usedComputers <= n && sumSmall >= (n - usedComputers) * time;
    };
    
    let left = 0;
    let right = Math.floor(batteries.reduce((sum, battery) => sum + battery, 0) / n);
    
    while (left < right) {
        const mid = Math.floor((left + right + 1) / 2);
        if (canRun(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × log(sum/n))，其中 m 是电池数量，sum 是电池总电量
空间复杂度O(1)

相关题目