目标
给你一个整数 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 <= 10^5
- 1 <= workerTimes.length <= 10^4
- 1 <= workerTimes[i] <= 10^6
思路
整数 mountainHeight 表示山的高度，workerTimes[i] 表示工人 i 的时效，工人 i 将山的高度降低 x 所需的时间是 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x，求工人同时工作，将山的高度降为 0 所需要的最少时间。
移山所需的时间是所有工人消耗时间的最大值，最小化这个最大值，可以考虑二分答案。
工人 i 将高度降低 x 所需时间为 workerTimes[i] * (1 + 2 + …… + x) = workerTimes[i] * (1 + x) * x / 2。如果最大时间是 target，解方程可得工人 i 最多将高度降低 (sqrt(1 + (8 * target) / workerTimes[i]) - 1) / 2，只需判断降低的高度是否超过 mountainHeight 即可。
代码
/**
* @date 2026-03-13 9:42
*/
public class MinNumberOfSeconds3296 {
public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
int max = 0;
int n = workerTimes.length;
for (int wt : workerTimes) {
max = Math.max(max, wt);
}
long p = (mountainHeight - 1) / n + 1;
long l = 0L, r = max * (1 + p) * p / 2;
long m = l + (r - l) / 2;
while (l <= r) {
if (check(mountainHeight, workerTimes, m)) {
r = m - 1;
} else {
l = m + 1;
}
m = l + (r - l) / 2;
}
return l;
}
public boolean check(int mountainHeight, int[] workerTimes, long target) {
int total = 0;
for (int w : workerTimes) {
total += (int) (Math.sqrt(1 + (8 * target) / w) - 1) / 2;
if (total >= mountainHeight) {
return true;
}
}
return false;
}
}
性能
