原题链接:
https://leetcode.cn/problems/maximal-score-after-applying-k-operations/

解法1 堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
    贪心 每次选最大的执行即可
    heap
*/

typedef long long LL;

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        // c++ 堆默认 大根堆
        // 值 以及 下标
        priority_queue<pair<LL,int>>heap;       

        for(int i = 0 ; i < nums.size() ; i++){
            heap.push(pair<LL,int>(nums[i],i));
        } 

        LL ans = 0;

        while(k){
            k--;
            auto x = heap.top();
            ans += x.first;
            heap.pop();
            // ceil c++上取整函数
            heap.push(pair<LL,int>(ceil(x.first/3.0), x.second));
        }

        return ans;
    }
};