Skip to content

3296. Minimum Number of Seconds to Make Mountain Height Zero

You are given an integer mountainHeight denoting the height of a mountain.

You are also given an integer array workerTimes representing the work time of workers in seconds.

The workers work simultaneously to reduce the height of the mountain. For worker i:

  • To decrease the mountain's height by x, it takes
workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x

seconds. For example:

  • To reduce the height of the mountain by 1, it takes workerTimes[i] seconds.
  • To reduce the height of the mountain by 2, it takes workerTimes[i] + workerTimes[i] * 2 seconds, and so on.

Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.

Example 1:

Input: mountainHeight = 4, workerTimes = [2,1,1]

Output: 3

Explanation:

One way the height of the mountain can be reduced to 0 is:

  • Worker 0 reduces the height by 1, taking workerTimes[0] = 2 seconds.
  • Worker 1 reduces the height by 2, taking workerTimes[1] + workerTimes[1] * 2 = 3 seconds.
  • Worker 2 reduces the height by 1, taking workerTimes[2] = 1 second.

Since they work simultaneously, the minimum time needed is max(2, 3, 1) = 3 seconds.

Example 2:

Input: mountainHeight = 10, workerTimes = [3,2,2,4]

Output: 12

Explanation:

  • Worker 0 reduces the height by 2, taking workerTimes[0] + workerTimes[0] * 2 = 9 seconds.
  • Worker 1 reduces the height by 3, taking workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 seconds.
  • Worker 2 reduces the height by 3, taking workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 seconds.
  • Worker 3 reduces the height by 2, taking workerTimes[3] + workerTimes[3] * 2 = 12 seconds.

The number of seconds needed is max(9, 12, 12, 12) = 12 seconds.

Example 3:

Input: mountainHeight = 5, workerTimes = [1]

Output: 15

Explanation:

There is only one worker in this example, so the answer is workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15.

Constraints:

  • 1 <= mountainHeight <= 105
  • 1 <= workerTimes.length <= 104
  • 1 <= workerTimes[i] <= 106

Solution:

class Solution {
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int maxT = 0;
        for (int t : workerTimes) {
            maxT = Math.max(maxT, t);
        }
        int h = (mountainHeight - 1) / workerTimes.length + 1;
        long left = 0;
        long right = (long) maxT * h * (h + 1) / 2;
        while (left + 1 < right) {
            long mid = (left + right) / 2;
            if (check(mid, mountainHeight, workerTimes)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(long m, int leftH, int[] workerTimes) {
        for (int t : workerTimes) {
            leftH -= (int) ((Math.sqrt(m / t * 8 + 1) - 1) / 2);
            if (leftH <= 0) {
                return true;
            }
        }
        return false;
    }
}

https://www.bilibili.com/video/BV1WRtDejEjD/?spm_id_from=333.999.0.0&vd_source=73e7d2c4251a7c9000b22d21b70f5635

class Solution {
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        Arrays.sort(workerTimes);

        int reduce = mountainHeight / workerTimes.length;
        // 10 /4 = 2;
        int still = mountainHeight - reduce * workerTimes.length;

        int[] store = new int[workerTimes.length];
        for (int i = 0; i < workerTimes.length; i++){
            store[i] = workerTimes[i] * ((1 + reduce) * reduce/2);


        }
        int j = 0;
        while(still > 0){
            store[j] = store[j] + workerTimes[j] * (reduce + 1);
            j++;
            still = still - 1;
        }

        int result = 0;
        for (int i = 0; i < store.length; i++){
            result = Math.max(result, store[i]);
        }

        return (long) result;
    }


}
// 300 / 571 testcases passed
// 应该逻辑部分错误了....

❌

看不出来这个应该用binary search...

断断续续的刷题 虽然该不会的还是不会 懵逼是日常... 但是奇怪的感受突然开始出现 I wanna finish ... 是不是在暗示我可以next level了

Rating 上2000是不是可以手撕面试题了