minimum-operations-to-exceed-threshold-value-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed integer array <code>nums</code>, and an integer <code>k</code>.

You are allowed to perform some operations on <code>nums</code>, where in a single operation, you can:

<ul>
	<li>Select the two smallest integers <code>x</code> and <code>y</code> from <code>nums</code>.</li>
	<li>Remove <code>x</code> and <code>y</code> from <code>nums</code>.</li>
	<li>Insert <code>(min(x, y) * 2 + max(x, y))</code> at any position in the array.</li>
</ul>

Note that you can only apply the described operation if <code>nums</code> contains at least two elements.

Return the minimum number of operations needed so that all elements of the array are greater than or equal to <code>k</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [2,11,10,1,3], k = 10

Output: 2

Explanation:

<ol>
	<li>In the first operation, we remove elements 1 and 2, then add <code>1 * 2 + 2</code> to <code>nums</code>. <code>nums</code> becomes equal to <code>[4, 11, 10, 3]</code>.</li>
	<li>In the second operation, we remove elements 3 and 4, then add <code>3 * 2 + 4</code> to <code>nums</code>. <code>nums</code> becomes equal to <code>[10, 11, 10]</code>.</li>
</ol>

At this stage, all the elements of nums are greater than or equal to 10 so we can stop.&nbsp;

It can be shown that 2 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.
</div>

Example 2:

<div class="example-block">
Input: nums = [1,1,2,4,9], k = 20

Output: 4

Explanation:

<ol>
	<li>After one operation, <code>nums</code> becomes equal to <code>[2, 4, 9, 3]</code>.&nbsp;</li>
	<li>After two operations, <code>nums</code> becomes equal to <code>[7, 4, 9]</code>.&nbsp;</li>
	<li>After three operations, <code>nums</code> becomes equal to <code>[15, 9]</code>.&nbsp;</li>
	<li>After four operations, <code>nums</code> becomes equal to <code>[33]</code>.</li>
</ol>

At this stage, all the elements of <code>nums</code> are greater than 20 so we can stop.&nbsp;

It can be shown that 4 is the minimum number of operations needed so that all elements of the array are greater than or equal to 20.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 2 * 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
	<li>The input is generated such that an answer always exists. That is, after performing some number of operations, all elements of the array are greater than or equal to <code>k</code>.</li>
</ul>

minOperations

Minimum Operations to Exceed Threshold Value II

Minimum Operations to Halve Array Sum

minimum-operations-to-halve-array-sum

将数组和减半的最少操作次数

Array

Simulation

Heap (Priority Queue)

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。

你可以对&nbsp;<code>nums</code>&nbsp;执行一些操作，在一次操作中，你可以：

<ul>
	<li>选择 <code>nums</code>&nbsp;中 最小 的两个整数&nbsp;<code>x</code> 和&nbsp;<code>y</code>&nbsp;。</li>
	<li>将&nbsp;<code>x</code> 和&nbsp;<code>y</code> 从&nbsp;<code>nums</code>&nbsp;中删除。</li>
	<li>将&nbsp;<code>min(x, y) * 2 + max(x, y)</code>&nbsp;添加到数组中的任意位置。</li>
</ul>

注意，只有当&nbsp;<code>nums</code>&nbsp;至少 包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都 大于或等于&nbsp;<code>k</code>&nbsp;，请你返回需要的&nbsp;最少&nbsp;操作次数。

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [2,11,10,1,3], k = 10

输出：2

解释：

<ol>
	<li>第一次操作中，我们删除元素 1 和 2 ，然后添加 <code>1 * 2 + 2</code> 到 <code>nums</code> 中，<code>nums</code> 变为 <code>[4, 11, 10, 3]</code> 。</li>
	<li>第二次操作中，我们删除元素 3 和 4 ，然后添加 <code>3 * 2 + 4</code> 到 <code>nums</code> 中，<code>nums</code> 变为 <code>[10, 11, 10]</code> 。</li>
</ol>

此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。

可以证明使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

&nbsp;
</div>

示例 2：

<div class="example-block">
输入：nums = [1,1,2,4,9], k = 20

输出：4

解释：

<ol>
	<li>第一次操作后，<code>nums</code> 变为 <code>[2, 4, 9, 3]</code>。</li>
	<li>第二次操作后，<code>nums</code> 变为 <code>[7, 4, 9]</code>。</li>
	<li>第三次操作后，<code>nums</code> 变为 <code>[15, 9]</code>。</li>
	<li>第四次操作后，<code>nums</code> 变为 <code>[33]</code>。</li>
</ol>

此时，<code>nums</code> 中的所有元素都大于等于 20 ，所以我们停止操作。

可以证明使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。
</div>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 2 * 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
	<li>输入保证答案一定存在，也就是说，在进行某些次数的操作后，数组中所有元素都大于等于&nbsp;<code>k</code> 。</li>
</ul>