2023-12-23每日一题

一、题目编号

1962. 移除石子使总数最小

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：

• 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。
  **注意：**你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后，剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。

示例 1：

示例 2：

提示：

• 1 <= piles.length <= 10⁵
• 1 <= piles[i] <= 10⁴
• 1 <= k <= 10⁵

四、解题代码

class Solution {
public:int minStoneSum(vector<int>& piles, int k) {priority_queue<int> pq(piles.begin(), piles.end());for (int i = 0; i < k; i++) {int pile = pq.top();pq.pop();pile -= pile / 2;pq.push(pile);}int sum = 0;while (!pq.empty()) {sum += pq.top();pq.pop();}return sum;}
};

五、解题思路

(1) 贪心+优先队列。