2530. 执行 K 次操作后的最大分数
- 题目
- 方法-【贪心】 & 题目特征-【找最值】
- 方法-【优先队列】 & 题目特征-【快速找最值】
题目
题目链接：https://leetcode.cn/problems/maximal-score-after-applying-k-operations/description/
输入：nums = [1,10,3,3,3], k = 3
输出：17
解释：可以执行下述操作：
第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。（10除以3向上取整为4）。分数增加 10 。
第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。（4除以3向上取整为2）。分数增加 4 。
第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。（3除以3向上取整为1）。分数增加 3 。
最后分数是 10 + 4 + 3 = 17 。
方法-【贪心】 & 题目特征-【找最值】
第一思路，就是贪心，选出当前最大的那个元素，更新数组，继续选出最大，循环 k 次。
class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
long long score = 0;
for (int i = 0; i < k; i++) {
long long maxIdx = max_element(nums.begin(), nums.end()) - nums.begin();
long long maxVal = nums[maxIdx];
score += maxVal;
nums[maxIdx] = ceil(maxVal / 3.0);
}
return score;
}
};测试用例通过了，但提交超出时间限制。
看到给的算例，k=100000，数组元素鼠标滚动半分钟还没到一半，真的好多。
方法-【优先队列】 & 题目特征-【快速找最值】
贪心是行的通，我们只需要寻找最大值，但是我们是从头到尾遍历，又因为数组是动态变化的，我们得每次都从头遍历。
我们可以用数据结构优化，用优先队列实现。
优先队列是一种抽象数据类型，它支持按照元素的优先级进行操作。最大堆和最小堆是优先队列的一种实现方式。
最大堆是一个完全二叉树，其中父节点的值大于或等于其子节点的值。最小堆则相反，父节点的值小于或等于其子节点的值。
在使用最大堆或最小堆实现优先队列时，通常会将优先级较高的元素放在堆的顶部，即根节点。
这样，当我们需要访问具有最高优先级的元素时，可以通过查看堆的根节点来获得。
最大堆还常用于解决一些需要快速找到最大值的问题，如找到一个数组中的第k大元素等。
最小堆在某些问题中也很有用，例如在一组数据中找到最小的k个元素等。
使用优先队列的好处，是从全局检索到局部检索，时间复杂度从 变成
。
优先队列应用很广。
比如游戏系统，需要做查询排名前N的需求。比如战斗力排名前十的玩家。
如果是全局排序的过程，在玩家很多时，效率会越来越低。
class Solution {
public:
long long maxKelements(vector<int> &nums, int k) {
priority_queue<int> pq(less<int>(), move(nums));
long long ans = 0;
while (k--) {
int x = pq.top();
pq.pop();
ans += x;
pq.push(ceil(x / 3.0));
}
return ans;
}
};