福建建设注册管理中心网站沧州网络推广管理公司

贪心+优先队列

请看答案需求：得到最大分数。易猜到，得到最大分数的取法是每次取数组中最大的数字(贪心思路)。

问题转化为：如何快速找到数组中最大的数字，根据问题规模$k=10^5$，维护优先队列即可$O(klo{g}_{2}n)$解决问题。

请看如下代码：

class Solution {
public:long long maxKelements(vector<int>& nums, int k) {// priority_queue<int> pq(nums.begin(), nums.end());priority_queue<int> pq(less<int>(), move(nums));long long ans = 0;while (k --) {int t = pq.top();pq.pop();ans += t;t = (t + 2) / 3;pq.push(t);}return ans;}
};

时间复杂度 $O(n+klogn)$：维护优先队列，的时间复杂度$O(n)$。

空间复杂度 $O(1)$：只使用常数级空间。

致语

• 理解思路很重要。
• 请读者放心留言，可以是疑惑的点，或者讨论！！墨染看到会回复的。