Leetcode—1962.移除石子使总数最小【中等】(最大堆做法)

2023-12-24 06:05:02

2023每日刷题(六十八)

Leetcode—1962.移除石子使总数最小

在这里插入图片描述

实现代码

class Solution {
public:
    void downAdjustHeap(vector<int>& arr, int low, int high) {
        int i = low, j = i * 2 + 1;
        while(j <= high) {
            if(j + 1 <= high && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            if(arr[j] > arr[i]) {
                swap(arr[i], arr[j]);
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }

    void createHeap(vector<int>& arr) {
        int n = arr.size();
        for(int i = n / 2 - 1; i >= 0; i--) {
            downAdjustHeap(arr, i, n - 1);
        }
    }

    int minStoneSum(vector<int>& piles, int k) {
        createHeap(piles);
        int n = piles.size();
        for(int i = 0; i < k; i++) {
            piles[0] -= piles[0] / 2;
            downAdjustHeap(piles, 0, n - 1);
        }
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += piles[i];
        }
        return sum;
    }
};

运行结果

在这里插入图片描述
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

文章来源:https://blog.csdn.net/qq_44631615/article/details/135169830
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。