2023-10-28每日一题

一、题目编号

2558. 从数量最多的堆取走礼物

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

• 选择礼物数量最多的那一堆。
• 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
• 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。

返回在 k 秒后剩下的礼物数量。

示例1：
示例2：

提示：

• 1 <= gifts.length <= 10³
• 1 <= gifts[i] <= 10⁹
• 1 <= k <= 10³

四、解题代码

class Solution {priority_queue<int> q;
public:long long pickGifts(vector<int>& gifts, int k) {for(int i = 0; i < gifts.size(); ++i){q.push(gifts[i]);}while(k != 0){k--;int num = q.top();q.pop();num = sqrt(num);q.push(num);}long long sum = 0;while(!q.empty()){sum += q.top();q.pop();}return sum;}
};

五、解题思路

(1) 队列