题目描述
你有 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 <= 1051 <= batteries[i] <= 109
解法
方法一：二分查找
我们注意到，如果我们可以让 \(n\) 台电脑同时运行 \(t\) 分钟，那么我们也可以让 \(n\) 台电脑同时运行 \(t' \le t\) 分钟，这存在着单调性。因此，我们可以使用二分查找的方法找到最大的 \(t\)。
我们定义二分查找的左边界 \(l=0\)，右边界 \(r=\sum_{i=0}^{n-1} batteries[i]\)。每次二分查找的过程中，我们使用一个变量 \(mid\) 表示当前的中间值，即 \(mid = (l + r + 1) >> 1\)。我们判断是否存在一种方案，使得 \(n\) 台电脑同时运行 \(mid\) 分钟。如果存在，那么我们就将 \(l\) 更新为 \(mid\)，否则我们将 \(r\) 更新为 \(mid - 1\)。最后，我们返回 \(l\) 即为答案。
问题转化为如何判断是否存在一种方案，使得 \(n\) 台电脑同时运行 \(mid\) 分钟。如果一个电池可以运行的分钟数大于 \(mid\)，由于电脑同时运行 \(mid\) 分钟，而一个电池同一时间只能供电一台电脑，因此我们只能使用这个电池 \(mid\) 分钟。如果一个电池可以运行的分钟数小于等于 \(mid\)，我们可以使用这个电池的全部电量。因此，我们统计所有电池可以供电的分钟数之和 \(s\)，如果 \(s \ge n \times mid\)，那么我们就可以使得 \(n\) 台电脑同时运行 \(mid\) 分钟。
时间复杂度 \(O(n \times \log M)\)，其中 \(M\) 为所有电池的电量之和，空间复杂度 \(O(1)\)。
| class Solution:
def maxRunTime(self, n: int, batteries: List[int]) -> int:
l, r = 0, sum(batteries)
while l < r:
mid = (l + r + 1) >> 1
if sum(min(x, mid) for x in batteries) >= n * mid:
l = mid
else:
r = mid - 1
return l
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public long maxRunTime(int n, int[] batteries) {
long l = 0, r = 0;
for (int x : batteries) {
r += x;
}
while (l < r) {
long mid = (l + r + 1) >> 1;
long s = 0;
for (int x : batteries) {
s += Math.min(mid, x);
}
if (s >= n * mid) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
long long maxRunTime(int n, vector<int>& batteries) {
long long l = 0, r = 0;
for (int x : batteries) {
r += x;
}
while (l < r) {
long long mid = (l + r + 1) >> 1;
long long s = 0;
for (int x : batteries) {
s += min(1LL * x, mid);
}
if (s >= n * mid) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func maxRunTime(n int, batteries []int) int64 {
l, r := 0, 0
for _, x := range batteries {
r += x
}
for l < r {
mid := (l + r + 1) >> 1
s := 0
for _, x := range batteries {
s += min(x, mid)
}
if s >= n*mid {
l = mid
} else {
r = mid - 1
}
}
return int64(l)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function maxRunTime(n: number, batteries: number[]): number {
let l = 0n;
let r = 0n;
for (const x of batteries) {
r += BigInt(x);
}
while (l < r) {
const mid = (l + r + 1n) >> 1n;
let s = 0n;
for (const x of batteries) {
s += BigInt(Math.min(x, Number(mid)));
}
if (s >= mid * BigInt(n)) {
l = mid;
} else {
r = mid - 1n;
}
}
return Number(l);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | impl Solution {
pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
let n = n as i64;
let mut l: i64 = 0;
let mut r: i64 = batteries.iter().map(|&x| x as i64).sum();
while l < r {
let mid = (l + r + 1) >> 1;
let mut s: i64 = 0;
for &x in &batteries {
let v = x as i64;
s += if v < mid { v } else { mid };
}
if s >= n * mid {
l = mid;
} else {
r = mid - 1;
}
}
l
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | public class Solution {
public long MaxRunTime(int n, int[] batteries) {
long l = 0, r = 0;
foreach (int x in batteries) {
r += x;
}
while (l < r) {
long mid = (l + r + 1) >> 1;
long s = 0;
foreach (int x in batteries) {
s += Math.Min(mid, (long)x);
}
if (s >= (long)n * mid) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
}
|