2530. 执行 K 次操作后的最大分数

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

在一步 操作 中：

选出一个满足 0 <= i < nums.length 的下标 i ，
将你的 分数 增加 nums[i] ，并且
将 nums[i] 替换为 ceil(nums[i] / 3) 。
返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

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

---

思路：

**贪心算法：**使用优先队列每次取出最大值。

重写贪心算法规则：
var q = new PriorityQueue((a,b)->b-a);
q.offer(num1); //加入元素
int num2 = q.poll(); //移除第一个元素

TreeMap与PriorityQueue的区别：

• 数据结构类型：
  PriorityQueue 是一种队列（Queue）数据结构，通常用于实现优先队列。它基于元素的优先级来确定元素的顺序，允许高优先级的元素在队列中排在低优先级元素的前面。
  TreeMap 是一种映射（Map）数据结构，它将键值对进行关联，并且根据键的顺序对它们进行排序。键是唯一的，且按升序排列。
• 应用场景：
  PriorityQueue 通常用于实现任务调度、事件处理、Dijkstra算法等需要按照优先级处理元素的情况。
  TreeMap 通常用于需要按键排序的情况，例如存储有序的关联数据或执行范围查询。
• 排序方式：
  PriorityQueue 基于元素的优先级来排序，通常采用最小堆或最大堆的方式。
  TreeMap 基于键对键值对进行排序。
• 数据结构特点：
  PriorityQueue 是一个队列，通常用数组或链表实现。它允许快速的插入和删除操作，但不支持范围查询。
  TreeMap 是一颗二叉搜索树，它支持快速查找、插入和删除操作，还支持范围查询，因为数据按照键有序排列。
• 复杂度：
  PriorityQueue 的插入和删除操作的时间复杂度为O(log n)，其中 n 是队列中的元素数量。
  TreeMap 的操作时间复杂度也是O(log n)。

class Solution {
    public long maxKelements(int[] nums, int k) {
        long ans = 0;
        var q = new PriorityQueue<Integer>((a, b)-> b-a);
        for(int num:nums) {
            q.offer(num);
        }
        while(k>0) {
            k --;
            int num = q.poll();
            ans = ans + num;
            q.offer((int)Math.ceil(num/3.0));            
        }
        return ans;        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16