贪心算法学习（共12题） ：1.柠檬水找零、2.将数组和减半的最少操作次数

1.柠檬水找零

一、题目解析

二、算法原理

有五块的话要，优先保留五块，优先选择10+5，没有的话在选择5+5+5.

三、代码

class Solution { public: bool lemonadeChange(vector<int>& bills) { int five = 0, ten = 0; for(auto x : bills) { if(x == 5) five++; else if(x == 10) { if(five == 0) return false; five--; ten++; } else { if(ten && five) // 贪心：优先用10元找零 { ten--; five--; } else if(five >= 3) { five -= 3; } else { return false; } } } return true; } };

四、证明

证明策略：交换论证法

当是5和10元时，贪心解和最优解没有差别

当是20时

2.将数组和减半的最少操作次数

一、题目解析

解法：贪心+大根堆

二、具体策略：

每次挑选当前数组中最大的那个数，然后减半，知道数组和减少到至少一半为止

三、代码

class Solution { public: int halveArray(vector<int>& nums) { priority_queue<double> heap; double sum = 0.0; for (int x : nums) { heap.push(x); sum += x; } sum /= 2.0; int count = 0; while (sum > 0) { double t = heap.top() / 2.0; heap.pop(); sum -= t; count++; heap.push(t); } return count; } };

四、证明

贪心解挑选的是最大的数，最优解可能不是，所以x>=y

1.如果x没用过，那么直接换，不影响（

y<x,y减半都能让数组变小，x更能让他变小，

哪怕后面用二分之y，四分之y，里面的y也可以替换为x不影响

）

2.如果x用过，先用x还是先用y交换位置并不影响

就算y与x之间存在二分之y，四分之y，里面的y也可以替换为x不影响

3.最大数

一.题目解析

二、