当前位置：首页 > news >正文

算法练习题24——leetcode3296移山所需的最小秒数（二分模拟）

news 2025/7/2 3:46:11

【题目描述】

【代码示例（java）】

class Solution {// 计算让工人们将山的高度降到0所需的最少时间public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {long left = 0; // 最少时间初始为0long right = 0; // 最大时间初始化为0// 计算每个工人在最坏情况下，单独完成整个山的工作所需的最大时间for (int workTime : workerTimes) {// workTime 是工人降低1个单位高度所需的时间// 公式计算从1降低到mountainHeight所需的总时间// 总工作量：1 + 2 + ... + mountainHeight = (mountainHeight * (mountainHeight + 1)) / 2// 总时间就是工人工作时间乘以这个总工作量right = Math.max(right, (long) workTime * (mountainHeight * (mountainHeight + 1L)) / 2L);}// 使用二分查找来寻找完成任务的最少时间// 这里的范围是 [left, right]while (left < right) {long mid = left + (right - left) / 2; // 计算中间时间，防止溢出// 检查在mid秒内是否可以完成任务if (can(mountainHeight, workerTimes, mid)) {right = mid; // 如果可以完成任务，缩小右边界} else {left = mid + 1; // 如果不能完成任务，增加左边界}}return left; // left即为最小的可以完成任务的时间}// 检查工人们能否在给定的time秒内将山的高度降到0private boolean can(int mountainHeight, int[] workerTimes, long time) {long totalReduceHeight = 0; // 总共降低的高度初始化为0// 遍历每个工人，计算他们在time秒内可以降低的最大高度for (int workTime : workerTimes) {long left = 0; // 当前工人能降低的最小高度初始化为0long right = mountainHeight; // 当前工人能降低的最大高度不会超过mountainHeight// 使用二分查找计算该工人在给定time秒内可以降低的最大高度while (left < right) {// 计算mid，这个mid是该工人可能降低的单位高度long mid = left + (right - left + 1) / 2; // 这里加1是为了偏向右边，避免死循环// 计算该工人降低mid个单位高度所需的时间：工作时间 * (1 + 2 + ... + mid)long requiredTime = workTime * mid * (mid + 1) / 2;// 如果当前时间够用，说明可以降低mid个单位高度if (requiredTime <= time) {left = mid; // 时间足够，增加高度} else {right = mid - 1; // 时间不足，降低高度}}// 当前工人能降低的最大高度是lefttotalReduceHeight += left; // 将该工人降低的高度累计到总高度上// 如果总的降低高度已经达到或超过山的高度，则任务可以完成，提前返回trueif (totalReduceHeight >= mountainHeight) {return true;}}// 如果所有工人合计降低的高度不足以将山的高度降为0，返回falsereturn totalReduceHeight >= mountainHeight;}
}