杭州网站开发建设,济宁市建设工程质量监督站网站,电子商务网站建设与维护ppt,怎么样做网站 用网站赚钱目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码运行结果#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一个数组#xff0c;我们每次可以将任意一个元素减半#xff0c;问我们操作几次之后才可以将整个数组的和减半…目录
题目
示例
分析
代码运行结果 题目 示例 分析
题目给我们一个数组我们每次可以将任意一个元素减半问我们操作几次之后才可以将整个数组的和减半这里的减半不是刚好减半而是至少减去一半所以我们多减一点是没关系的。
如果题目涉及到什么最大最小最多最少那么我们大概率都是要用到贪心的思想。
既然要操作次数最小那么我们每次把元素减半都应该尽量多减少一点所以每次减少元素的一半我们都应该把数组里最大的元素给减半。
那么我们就可以使用优先队列大顶堆来帮助我们维护数组的最大元素然后每次把队列顶端最大的数拿出来减半以后再放回去并且把数组和对应的减去这个元素的一半。
如此循环操作直到数组和成功减半我们返回次数即可。 代码运行结果
class Solution {
public:int halveArray(vectorint nums) {double SUM0;priority_queuedoublepq; //大顶堆(优先队列)for(const int num:nums){ //统计总和并进入大顶堆SUMnum;pq.push(num);}double targetSUM/2.0; //获取总和的一半int res0;while(SUMtarget){ //不断循环直到SUM减半.res;//获取栈顶(最大元素),把最大元素减半才能减少最多数double temppq.top(); pq.pop();temp/2.0;SUM-temp; //总和减去该元素的一半pq.push(temp); //减半后继续进入大顶堆}return res;}
};
