LeetCode - 移除石子使总数最小

作者：从前慢现在也慢 | 2024-04-05 11:33:55

踩

1962. 移除石子使总数最小

当我看到这道题目的时候，第一时间想到的是：while循环 + sort，时间复杂度 k*nlogn。题目要求执行k次操作后，剩下狮子的最小总数，我们是否可以考虑维护一个堆呢？堆顶值最大，只要对堆顶做操作就行了。


class Solution {
public:
    int minStoneSum(vector<int>& p, int k) {
        make_heap(p.begin(), p.end());
        while (k-- && p[0] != 1)
        {
            pop_heap(p.begin(), p.end());
            p.back() -= p.back() / 2;
            push_heap(p.begin(), p.end());
        }
        
        return accumulate(p.begin(), p.end(), 0);
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/365312