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

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

article 2024/11/15 4:20:04

【题目描述】

【代码示例（java）】

class Solution {
    
    // 计算让工人们将山的高度降到0所需的最少时间
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        long left = 0; // 最少时间初始为0
        long 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秒内将山的高度降到0
    private boolean can(int mountainHeight, int[] workerTimes, long time) {
        long totalReduceHeight = 0; // 总共降低的高度初始化为0

        // 遍历每个工人，计算他们在time秒内可以降低的最大高度
        for (int workTime : workerTimes) {
            long left = 0; // 当前工人能降低的最小高度初始化为0
            long 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; // 时间不足，降低高度
                }
            }

            // 当前工人能降低的最大高度是left
            totalReduceHeight += left; // 将该工人降低的高度累计到总高度上

            // 如果总的降低高度已经达到或超过山的高度，则任务可以完成，提前返回true
            if (totalReduceHeight >= mountainHeight) {
                return true;
            }
        }

        // 如果所有工人合计降低的高度不足以将山的高度降为0，返回false
        return totalReduceHeight >= mountainHeight;
    }
}