【算法】Maximal Score After Applying K Operations 执行 K 次操作后的最大分数-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Maximal Score After Applying K Operations 执行 K 次操作后的最大分数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Maximal Score After Applying K Operations 执行 K 次操作后的最大分数

问题描述：

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

在一步操作中：

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

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

$1 <= nums.length, k <= 10^9\\ 1 <= nums[i] <= 10^9$

分析

这是一个思路简单的模拟问题，每次可以选一个元素进行一次累加，然后把该元素的1/3放回去.

目标是在k次操作后可以得到的最大分数。

为了使k次操作最大，那么每次都应该选择集合中的最大值。
但是操作后，原始数据会变小，整个数组又需要找一次最大。
一般的做法就是每一次对n个元素重新排序，时间复杂度 $O(N\log N)$ ,一共要k次，整体的时间复杂度 $O(kN\log N)$ .

所以也就只能使用大顶堆来处理这个问题，每次的排序时间复杂度 $O(\log N)$ ,整体的时间复杂度 $O(k\log N)$ .

代码

public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->{return b-a;});
        for(int i: nums){
            pq.offer(i);
        }
        int cnt =0;
        long ans =0;
        while(cnt<k){
            cnt++;
            int t = pq.poll();
            ans +=t;
            int x = (t+2)/3;
            pq.offer(x);
        }
        return ans;
    }