LC.P2530[执行K次操作后的最大分数]

方法一：优先队列(大根堆)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public long maxKelements(int[] nums, int k) {
        long ans = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            q.offer(num);
        }
        while (k-- > 0) {
            int x = q.poll();
            ans += x;
            q.offer((x + 2) / 3);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n + klogn)$
  • 空间复杂度：$O(n)$