题目描述
给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
- 山的高度降低
x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如： - 山的高度降低 1，需要
workerTimes[i] 秒。 - 山的高度降低 2，需要
workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
示例 1：
输入： mountainHeight = 4, workerTimes = [2,1,1]
输出： 3
解释：
将山的高度降低到 0 的一种方式是：
- 工人 0 将高度降低 1，花费
workerTimes[0] = 2 秒。 - 工人 1 将高度降低 2，花费
workerTimes[1] + workerTimes[1] * 2 = 3 秒。 - 工人 2 将高度降低 1，花费
workerTimes[2] = 1 秒。
因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。
示例 2：
输入： mountainHeight = 10, workerTimes = [3,2,2,4]
输出： 12
解释：
- 工人 0 将高度降低 2，花费
workerTimes[0] + workerTimes[0] * 2 = 9 秒。 - 工人 1 将高度降低 3，花费
workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。 - 工人 2 将高度降低 3，花费
workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。 - 工人 3 将高度降低 2，花费
workerTimes[3] + workerTimes[3] * 2 = 12 秒。
所需的最少时间为 max(9, 12, 12, 12) = 12 秒。
示例 3：
输入： mountainHeight = 5, workerTimes = [1]
输出： 15
解释：
这个示例中只有一个工人，所以答案是 workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15 秒。
提示：
1 <= mountainHeight <= 1051 <= workerTimes.length <= 1041 <= workerTimes[i] <= 106
解法
方法一：二分查找
我们注意到，如果所有的工人能在 \(t\) 秒内将山的高度降低到 \(0\)，那么对于任意 \(t' > t\)，工人们也能在 \(t'\) 秒内将山的高度降低到 \(0\)。因此，我们可以使用二分查找的方法找到最小的 \(t\)，使得工人们能在 \(t\) 秒内将山的高度降低到 \(0\)。
我们定义一个函数 \(\textit{check}(t)\)，表示工人们能否在 \(t\) 秒内将山的高度降低到 \(0\)。具体地，我们遍历每一个工人，对于当前工人 \(\textit{workerTimes}[i]\)，假设他在 \(t\) 秒内降低了 \(h'\) 的高度，那么我们可以得到一个不等式：
\[ \left(1 + h'\right) \cdot \frac{h'}{2} \cdot \textit{workerTimes}[i] \leq t \]
解不等式得到：
\[ h' \leq \left\lfloor \sqrt{\frac{2t}{\textit{workerTimes}[i]} + \frac{1}{4}} - \frac{1}{2} \right\rfloor \]
我们可以将所有工人的 \(h'\) 相加，得到总共降低的高度 \(h\)，如果 \(h \geq \textit{mountainHeight}\)，那么说明工人们能在 \(t\) 秒内将山的高度降低到 \(0\)。
接下来，我们确定二分查找的左边界 \(l = 1\)，由于最少有一个工作，且每个工人的工作时间不超过 \(10^6\)，要想使山的高度降低到 \(0\)，最少需要 \((1 + \textit{mountainHeight}) \cdot \textit{mountainHeight} / 2 \cdot \textit{workerTimes}[i] \leq 10^{16}\) 秒，因此我们可以确定二分查找的右边界 \(r = 10^{16}\)。然后我们不断地将区间 \([l, r]\) 二分，直到 \(l = r\)，此时 \(l\) 即为答案。
时间复杂度 \(O(n \times \log M)\)，其中 \(n\) 为工人的数量，而 \(M\) 为二分查找的右边界，本题中 \(M = 10^{16}\)。空间复杂度 \(O(1)\)。
| class Solution:
def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
def check(t: int) -> bool:
h = 0
for wt in workerTimes:
h += int(sqrt(2 * t / wt + 1 / 4) - 1 / 2)
return h >= mountainHeight
return bisect_left(range(10**16), True, key=check)
|
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
26
27 | class Solution {
private int mountainHeight;
private int[] workerTimes;
public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
this.mountainHeight = mountainHeight;
this.workerTimes = workerTimes;
long l = 1, r = (long) 1e16;
while (l < r) {
long mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
private boolean check(long t) {
long h = 0;
for (int wt : workerTimes) {
h += (long) (Math.sqrt(t * 2.0 / wt + 0.25) - 0.5);
}
return h >= mountainHeight;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public:
long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
using ll = long long;
ll l = 1, r = 1e16;
auto check = [&](ll t) -> bool {
ll h = 0;
for (int& wt : workerTimes) {
h += (long long) (sqrt(t * 2.0 / wt + 0.25) - 0.5);
}
return h >= mountainHeight;
};
while (l < r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
|
| func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
return int64(sort.Search(1e16, func(t int) bool {
var h int64
for _, wt := range workerTimes {
h += int64(math.Sqrt(float64(t)*2.0/float64(wt)+0.25) - 0.5)
}
return h >= int64(mountainHeight)
}))
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | function minNumberOfSeconds(mountainHeight: number, workerTimes: number[]): number {
const check = (t: bigint): boolean => {
let h = BigInt(0);
for (const wt of workerTimes) {
h += BigInt(Math.floor(Math.sqrt((Number(t) * 2.0) / wt + 0.25) - 0.5));
}
return h >= BigInt(mountainHeight);
};
let l = BigInt(1);
let r = BigInt(1e16);
while (l < r) {
const mid = (l + r) >> BigInt(1);
if (check(mid)) {
r = mid;
} else {
l = 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
26
27
28
29
30
31 | impl Solution {
pub fn min_number_of_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
let mut l: i64 = 1;
let mut r: i64 = 10_i64.pow(16);
let check = |t: i64| -> bool {
let mut h: i64 = 0;
for &wt in &worker_times {
let wt = wt as f64;
let t_f = t as f64;
let val = ((t_f * 2.0 / wt + 0.25).sqrt() - 0.5).floor() as i64;
h += val;
if h >= mountain_height as i64 {
return true;
}
}
h >= mountain_height as i64
};
while l < r {
let mid = (l + r) >> 1;
if check(mid) {
r = mid;
} else {
l = 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
26
27
28 | /**
* @param {number} mountainHeight
* @param {number[]} workerTimes
* @return {number}
*/
var minNumberOfSeconds = function (mountainHeight, workerTimes) {
const check = t => {
let h = 0n;
for (const wt of workerTimes) {
h += BigInt(Math.floor(Math.sqrt((Number(t) * 2.0) / wt + 0.25) - 0.5));
}
return h >= BigInt(mountainHeight);
};
let l = 1n;
let r = 10000000000000000n;
while (l < r) {
const mid = (l + r) >> 1n;
if (check(mid)) {
r = mid;
} else {
l = 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
26
27
28 | public class Solution {
public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes) {
long l = 1, r = (long)1e16;
bool Check(long t) {
long h = 0;
foreach (int wt in workerTimes) {
long val = (long)(Math.Sqrt(t * 2.0 / wt + 0.25) - 0.5);
h += val;
if (h >= mountainHeight) {
return true;
}
}
return h >= mountainHeight;
}
while (l < r) {
long mid = (l + r) >> 1;
if (Check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
|