You have `n`

computers. You are given the integer `n`

and a **0-indexed** integer array `batteries`

where the `i`

battery can ^{th}**run** a computer for `batteries[i]`

minutes. You are interested in running **all** `n`

computers **simultaneously** using the given batteries.

Initially, you can insert **at most one battery** into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery **any number of times**. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return *the maximum number of minutes you can run all the *

`n`

*computers simultaneously.*

**Example 1:**

Input:n = 2, batteries = [3,3,3]Output:4Explanation:Initially, insert battery 0 into the first computer and battery 1 into the second computer. After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute. At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead. By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running. We can run the two computers simultaneously for at most 4 minutes, so we return 4.

**Example 2:**

Input:n = 2, batteries = [1,1,1,1]Output:2Explanation:Initially, insert battery 0 into the first computer and battery 2 into the second computer. After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running. We can run the two computers simultaneously for at most 2 minutes, so we return 2.

**Constraints:**

`1 <= n <= batteries.length <= 10`

^{5}`1 <= batteries[i] <= 10`

^{9}

**Solution: Binary Search**

Find the smallest L that we can not run, ans = L – 1.

For a guessing m, we check the total battery powers T = sum(min(m, batteries[i])), if T >= m * n, it means there is a way (doesn’t need to figure out how) to run n computers for m minutes by fully unitize those batteries.

Proof: If T >= m*n holds, there are two cases:

- There are only n batteries, can not swap, but each of them has power >= m.
- At least one of the batteries have power less than m, but there are more than n batteries and total power is sufficient, we can swap them with others.

Time complexity: O(Slogn) where S = sum(batteries)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: long long maxRunTime(int n, vector<int>& batteries) { long long l = 0; long long r = accumulate(begin(batteries), end(batteries), 0LL) + 1; while (l < r) { long long m = l + (r - l) / 2; long long t = 0; for (long long b : batteries) t += min(m, b); if (m * n > t) // smallest m that does not fit. r = m; else l = m + 1; } return l - 1; // greatest m that fits. } }; |

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。

如果您喜欢这篇文章／视频，欢迎您捐赠花花。

If you like my articles / videos, donations are welcome.

## Be First to Comment