领动网站建设,网站制作公司网站源码,前端菜鸟教程,dede网站版权信息【题目描述】 【代码示例#xff08;java#xff09;】
class Solution {// 计算让工人们将山的高度降到0所需的最少时间public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {long left 0; // 最少时间初始为0long right 0; // 最大时间初始化为0// …【题目描述】 【代码示例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;}
}【最大值公式】
就是一个等差数列求和加 L 是为了确保该数字被视为 long 类型这样可以避免在大数计算时溢出的问题。在这道题的情况下mountainHeight 可能会很大因此在某些运算中需要将其转换为 long 类型来确保计算的正确性。
好难 我要缺氧了谁来救我 谁 来 救救 本 小 主 哭.....
