maximal-score-after-applying-k-operations

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 have a starting score of <code>0</code>.

In one operation:

<ol>
	<li>choose an index <code>i</code> such that <code>0 &lt;= i &lt; nums.length</code>,</li>
	<li>increase your score by <code>nums[i]</code>, and</li>
	<li>replace <code>nums[i]</code> with <code>ceil(nums[i] / 3)</code>.</li>
</ol>

Return the maximum possible score you can attain after applying exactly <code>k</code> operations.

The ceiling function <code>ceil(val)</code> is the least integer greater than or equal to <code>val</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [10,10,10,10,10], k = 5
Output: 50
Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.
</pre>

Example 2:

<pre>
Input: nums = [1,10,3,3,3], k = 3
Output: 17
Explanation: You can do the following operations:
Operation 1: Select i = 1, so nums becomes [1,4,3,3,3]. Your score increases by 10.
Operation 2: Select i = 1, so nums becomes [1,2,3,3,3]. Your score increases by 4.
Operation 3: Select i = 2, so nums becomes [1,2,1,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length, k &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

maxKelements

Maximal Score After Applying K Operations

Sliding Window Maximum

sliding-window-maximum

滑动窗口最大值

Remove Stones to Minimize the Total

remove-stones-to-minimize-the-total

移除石子使总数最小

Greedy

Array

Heap (Priority Queue)

给你一个下标从 0 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。你的 起始分数 为 <code>0</code> 。

在一步 操作 中：

<ol>
	<li>选出一个满足 <code>0 &lt;= i &lt; nums.length</code> 的下标 <code>i</code> ，</li>
	<li>将你的 分数 增加 <code>nums[i]</code> ，并且</li>
	<li>将 <code>nums[i]</code> 替换为 <code>ceil(nums[i] / 3)</code> 。</li>
</ol>

返回在 恰好 执行 <code>k</code> 次操作后，你可能获得的最大分数。

向上取整函数 <code>ceil(val)</code> 的结果是大于或等于 <code>val</code> 的最小整数。

&nbsp;

示例 1：

<pre>
输入：nums = [10,10,10,10,10], k = 5
输出：50
解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。
</pre>

示例 2：

<pre>
输入：nums = [1,10,3,3,3], k = 3
输出：17
解释：可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,2,1,3,3] 。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length, k &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>