原文链接: https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total
英文原文
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:
- Choose any
piles[i]and removefloor(piles[i] / 2)stones from it.
Notice that you can apply the operation on the same pile more than once.
Return the minimum possible total number of stones remaining after applying the k operations.
floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).
Example 1:
Input: piles = [5,4,9], k = 2 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [5,4,5]. - Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12.
Example 2:
Input: piles = [4,3,6,7], k = 3 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [4,3,3,7]. - Apply the operation on pile 3. The resulting piles are [4,3,3,4]. - Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.
Constraints:
1 <= piles.length <= 1051 <= piles[i] <= 1041 <= k <= 105
中文题目
给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：
- 选出任一石子堆
piles[i]，并从中 移除floor(piles[i] / 2)颗石子。
注意：你可以对 同一堆 石子多次执行此操作。
返回执行 k 次操作后，剩下石子的 最小 总数。
floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。
示例 1：
输入：piles = [5,4,9], k = 2 输出：12 解释：可能的执行情景如下： - 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。 - 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。 剩下石子的总数为 12 。
示例 2：
输入：piles = [4,3,6,7], k = 3 输出：12 解释：可能的执行情景如下： - 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。 - 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。 - 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。 剩下石子的总数为 12 。
提示：
1 <= piles.length <= 1051 <= piles[i] <= 1041 <= k <= 105
通过代码
高赞题解
在周赛评论区看到有个兄弟说js没有内置堆很不友好。但其实，解此题堆并不是必须的，我们完全可以不使用任何相对高级的数据结构。
我们肯定需要一个数据结构来帮助我们找到剩余石头的最大值。
一个朴素的想法是我们将每次删除后的石头重新插入原来的有序序列，但显然插入排序会退化至$O(KN)$，这个时间复杂度无法接受。但仔细思考，由于我们每次总是将当前剩余最大的石头删掉一半，因此这个重新插回去的值也是有序的，它一定是非递增的！
因此，假设我们原有的石头还剩下X堆，被扔过后的都存在一起，还剩下Y堆，那么接下来要扔哪个呢？只能要么是原有的最大的，要么是之前被扔过的里面的最大的。而原有石头的最大值，可以通过预先排序来$O(1)$找到。而已经被扔过的部分中，由于它的大小一定是按操作时间不递增的，所以最大值必然是最早扔过的。
也就是说，我们需要一个数据结构，他支持插入新的元素，同时删除最早加入的元素，这不就是队列嘛！最普普通通的那种先入先出的队列嘛！
由此我们得到了不使用堆的解法：
1.将原数组排序
2.使用队列来保存所有曾经被扔掉一半的石头
3.扔掉所有石头中最大的一半，它只可能是原数组中的最后一个，或者队列里的第一个。将这堆石头从原有的数据结构中删除，减少一半后加入队列。
4.将步骤3重复k次后，统计剩余石头的总和。（或者预先统计总和，在步骤3中扣除扔掉的石头数）
此解法时间复杂度$O(NlogN+K)$，堆的解法为$O(N+KlogN)$，在K小于N的时候应该更有优势。
class Solution {
public:
int minStoneSum(vector<int>& piles, int k)
{
// 首先将原数组排序
sort(piles.begin() , piles.end());
// 使用队列来储存被扔掉过的石头
queue<int> q;
// 指向原有石头的末尾，当它前移时代表之前的元素被删除。当然直接pop_back也是可以的。
auto now = piles.rbegin();
// 当前最大的石头和剩余石头总和
int tmp , ans = 0;
for(auto i : piles)
ans += i;
while(k--)
{
// 若还未扔过石头或原有石头的最大值大于被扔过石头的最大值时，需要扔掉原有石头里最大的，也就是now指向的那堆
// 将反向迭代器now前移，表示这对石头被扔掉了
if(q.empty() || (!q.empty() && now != piles.rend() && *now > q.front()))
tmp = *now++;
// 否则将要扔掉的石头应该位于队列的头部，将它出队
else
{
tmp = q.front();
q.pop();
}
// 将取出的石头扔掉一半后加入队列，并在总和里扣除扔掉的部分
q.push(tmp - tmp / 2);
ans -= tmp / 2;
}
return ans;
}
};
另外，由于本题的石子大小范围只有10000，我们也完全可以利用类似于桶排序+单调指针的方式来模拟取出的过程，该做法的时间复杂度为$O(N+M+K)$，其中$M=10000$。
class Solution {
public:
int minStoneSum(vector<int>& piles, int k)
{
int ans = 0;
int s[10010] = {0};
for(auto i : piles)
{
s[i]++;
ans += i;
}
for(int i = 10000 , j ; k > 0 ; k-- , i = j)
{
for(j = i ; s[j] == 0 ; j--);
ans -= j / 2;
s[j] --;
s[j - j / 2] ++;
}
return ans;
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 5887 | 13498 | 43.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
