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

1.柠檬水找零一、题目解析二、算法原理有五块的话要优先保留五块优先选择105没有的话在选择555.三、代码class Solution { public: bool lemonadeChange(vectorint 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(vectorint nums) { priority_queuedouble 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; } };四、证明贪心解挑选的是最大的数最优解可能不是所以xy1.如果x没用过那么直接换不影响yx,y减半都能让数组变小x更能让他变小哪怕后面用二分之y四分之y里面的y也可以替换为x不影响2.如果x用过先用x还是先用y交换位置并不影响就算y与x之间存在二分之y四分之y里面的y也可以替换为x不影响3.最大数一.题目解析二、