leeetcode_2530 执行k次操作后的最大分数

1. 题意

给定一个整数数组，每次可以取出一个数累加并丢弃，并将该数的1/3 向上取整放回。
执行k次操作后的最大分数

2. 题解

每次取插入后的最大值，所以需要大根堆。

STL里面用priority_queue pq默认大根堆。

小根堆priority_queue, greater<> > pq，可以直接用容器进行初始化。

priority_queue pq(nums.begin(), nums.end())

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        
        priority_queue< int, vector<int>, less<> > pq;

        for ( auto &v : nums)
            pq.push(v);

        long long ans = 0;
        for ( int i = 0; i < k; ++i) {
            int v = pq.top();
            pq.pop();
            ans += v;
            pq.push( (v + 2)/3);
        }

        return ans; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20