minimum-number-of-seconds-to-make-mountain-height-zero

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Can we use binary search to solve this problem?

Do a binary search on the number of seconds to check if it's enough to reduce the mountain height to 0 or less with all workers working simultaneously.

Algorithms

You are given an integer <code>mountainHeight</code> denoting the height of a mountain.

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

Each worker may reduce the mountain&#39;s height by any non-negative integer amount. If worker <code data-end="170" data-start="167">i</code> reduces the height by <code data-end="196" data-start="193">x</code>, then:

<ul data-end="415" data-start="208">
	<li data-end="275" data-section-id="66oopy" data-start="208">reducing the first unit of height takes <code data-end="266" data-start="250">workerTimes[i]</code> seconds,</li>
	<li data-end="340" data-section-id="9o9grm" data-start="278">reducing the second unit takes <code data-end="331" data-start="311">workerTimes[i] * 2</code> seconds,</li>
	<li data-end="348" data-section-id="1o23ba" data-start="343">...</li>
	<li data-end="413" data-section-id="1brl21f" data-start="351">reducing the <code data-end="369" data-start="366">x</code>-th unit takes <code data-end="404" data-start="384">workerTimes[i] * x</code> seconds.</li>
</ul>

The total time spent by worker <code data-end="452" data-start="449">i</code> is the sum of the times required for all <code data-end="497" data-start="494">x</code> units they reduce.&nbsp;As all workers operate simultaneously, the total time required is the maximum time spent by any worker.

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

&nbsp;
Example 1:

<div class="example-block">
Input: mountainHeight = 4, workerTimes = [2,1,1]

Output: 3

Explanation:

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

<ul>
	<li>Worker 0 reduces the height by 1, taking <code>workerTimes[0] = 2</code> seconds.</li>
	<li>Worker 1 reduces the height by 2, taking <code>workerTimes[1] + workerTimes[1] * 2 = 3</code> seconds.</li>
	<li>Worker 2 reduces the height by 1, taking <code>workerTimes[2] = 1</code> second.</li>
</ul>

Since they work simultaneously, the minimum time needed is <code>max(2, 3, 1) = 3</code> seconds.
</div>

Example 2:

<div class="example-block">
Input: mountainHeight = 10, workerTimes = [3,2,2,4]

Output: 12

Explanation:

<ul>
	<li>Worker 0 reduces the height by 2, taking <code>workerTimes[0] + workerTimes[0] * 2 = 9</code> seconds.</li>
	<li>Worker 1 reduces the height by 3, taking <code>workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12</code> seconds.</li>
	<li>Worker 2 reduces the height by 3, taking <code>workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12</code> seconds.</li>
	<li>Worker 3 reduces the height by 2, taking <code>workerTimes[3] + workerTimes[3] * 2 = 12</code> seconds.</li>
</ul>

The number of seconds needed is <code>max(9, 12, 12, 12) = 12</code> seconds.
</div>

Example 3:

<div class="example-block">
Input: mountainHeight = 5, workerTimes = [1]

Output: 15

Explanation:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= mountainHeight &lt;= 105</code></li>
	<li><code>1 &lt;= workerTimes.length &lt;= 104</code></li>
	<li><code>1 &lt;= workerTimes[i] &lt;= 106</code></li>
</ul>

第 416 场周赛

weekly-contest-416

minNumberOfSeconds

资深工程师

Minimum Number of Seconds to Make Mountain Height Zero

Greedy

Array

Math

Binary Search

Heap (Priority Queue)

给你一个整数 <code>mountainHeight</code> 表示山的高度。

同时给你一个整数数组 <code>workerTimes</code>，表示工人们的工作时间（单位：秒）。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 <code>i</code> :

<ul>
	<li>山的高度降低 1，需要 <code>workerTimes[i]</code> 秒。</li>
	<li>山的高度降低 2，需要 <code>workerTimes[i] * 2</code> 秒。</li>
	<li>...</li>
	<li>山的高度降低 <code>x</code>，需要 <code>workerTimes[i] * x</code> 秒。</li>
</ul>

工人 <code>i</code> 所花费的总时间是所有 <code>x</code> 单位所需时间的总和。由于所有工人同时操作，所需的总时间是任何工人花费的 最大 时间。

返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。

&nbsp;

示例 1：

<div class="example-block">
输入： mountainHeight = 4, workerTimes = [2,1,1]

输出： 3

解释：

将山的高度降低到 0 的一种方式是：

<ul>
	<li>工人 0 将高度降低 1，花费 <code>workerTimes[0] = 2</code> 秒。</li>
	<li>工人 1 将高度降低 2，花费 <code>workerTimes[1] + workerTimes[1] * 2 = 3</code> 秒。</li>
	<li>工人 2 将高度降低 1，花费 <code>workerTimes[2] = 1</code> 秒。</li>
</ul>

因为工人同时工作，所需的最少时间为 <code>max(2, 3, 1) = 3</code> 秒。
</div>

示例 2：

<div class="example-block">
输入： mountainHeight = 10, workerTimes = [3,2,2,4]

输出： 12

解释：

<ul>
	<li>工人 0 将高度降低 2，花费 <code>workerTimes[0] + workerTimes[0] * 2 = 9</code> 秒。</li>
	<li>工人 1 将高度降低 3，花费 <code>workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12</code> 秒。</li>
	<li>工人 2 将高度降低 3，花费 <code>workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12</code> 秒。</li>
	<li>工人 3 将高度降低 2，花费 <code>workerTimes[3] + workerTimes[3] * 2 = 12</code> 秒。</li>
</ul>

所需的最少时间为 <code>max(9, 12, 12, 12) = 12</code> 秒。
</div>

示例 3：

<div class="example-block">
输入： mountainHeight = 5, workerTimes = [1]

输出： 15

解释：

这个示例中只有一个工人，所以答案是 <code>workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15</code> 秒。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= mountainHeight &lt;= 105</code></li>
	<li><code>1 &lt;= workerTimes.length &lt;= 104</code></li>
	<li><code>1 &lt;= workerTimes[i] &lt;= 106</code></li>
</ul>

移山所需的最少秒数

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

 * 山的高度降低 1，需要 workerTimes[i] 秒。
 * 山的高度降低 2，需要 workerTimes[i] * 2 秒。
 * ...
 * 山的高度降低 x，需要 workerTimes[i] * x 秒。

工人 i 所花费的总时间是所有 x 单位所需时间的总和。由于所有工人同时操作，所需的总时间是任何工人花费的 最大 时间。

返回一个整数，表示工人们使山的高度降低到 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 <= 105
 * 1 <= workerTimes.length <= 104
 * 1 <= workerTimes[i] <= 106