【贪心算法】day1

📝前言说明：

• 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）这个贪心算法正确性的证明
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

点击链接 开始学习 贪心day1 贪心day2 贪心day3 贪心day4 贪心day5 贪心day6 贪心day7 贪心day8 贪心day9 贪心day10

也可以点击下面连接，学习其他算法

点击链接 开始学习 优选专题 动态规划 递归、搜索与回溯 贪心算法

题目

• 贪心算法导论
• 860. 柠檬水找零
• • 优质解
  • 证明
• 2208. 将数组和减半的最少操作次数
• • 个人解
  • 证明

---

贪心算法导论

贪心策略的核心思想：局部最优 当做 全局最优

1. 把解决问题的过程分为若干步
2. 解决每一步时，都选择当前看起来 “最优的” 解法
3. “希望” 这个局部最优是全局最优

贪心算法的特点：

1. 根据 “贪心策略” 得到的结果可能是错误的
2. 正确的 “贪心策略” 需要证明 “正确性”
3. 不同题目的贪心策略不同，把我们遇到的贪心策略当 “经验” 来看就好

---

860. 柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/description/

---

优质解

思路：

• 问题分析（一杯柠檬水5元）：找零问题可以分情况讨论
  • 5 元 → 不用找，直接收下
  • 10 元 → 收下，且找 5元
  • 20 元 → 收下，找10 + 5 or 5 * 3
• 前两种情况是固定找法，只有20的时候有选择，此时最优解是：优先找10 + 5（这就是本题的贪心策略）

代码：

class Solution {public: bool lemonadeChange(vector<int>& bills) { int arr[2]; // 用来存放 5, 10 元的数量 memset(arr, 0, sizeof(arr)); for(auto b: bills) { if(b == 5) arr[0]++; else if(b == 10) { arr[1]++; arr[0]--; } else { if(arr[1] > 0) // 有 10 块的优先找10块的 {  arr[1]--;  arr[0]--; } else  arr[0] -= 3; } if(arr[0] < 0) return false; } return true; }};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

证明

利用：交换论证法
原理：在不破坏最优解的 “最优性质” 的前提下，将最优解调整成贪心解，则代表这个贪心解是正确的

在这个问题中：只有遇到 20 元的时候才需要考虑策略：

• 贪心策略：有 10 就优先 10 + 5
• 最优策略：每次找20：可能 10 + 5 或 5 + 5 + 5（未知的）

最优策略中：当选择 5 + 5 + 5 的时候，如果有多的10块钱，此时可以用10元替换一个 5 + 5，（此时，最优解依然是最优解，即：依然可以保证能够找零成功，所以这个最优解可以调整为贪心解）

---

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

题目链接：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/

个人解

思路：

• 每次选最大的来减小一半
• 意味着要排序，可以利用大根堆

屎山代码：

class Solution {public: int halveArray(vector<int>& nums) { priority_queue<double> arr; double sum = 0; for(auto x: nums) { sum += x; arr.push(x); } double cur = sum; int count = 0; while(cur > sum / 2) { count++; double max = arr.top(); arr.pop(); cur -= max / 2; arr.push(max / 2); } return count; }};

时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$

证明

依旧是：交换论证法

• 某次选择中，若：最优解中选择的数 x < 贪心中的 y
• 易知，此x可用y替换

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！