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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!