题目特点?-怎么判断一道题适合使用greedy?
“最”–付出最少,得到最多->贪心是目的:想用最少的投入获得最大回报“给后面的选择留下最大余地,能确保全局最优”解题思路?
流程:
局部最优 => 前面的选择给后面的选择留下最大余地(比如:留下尽可能多的饼干||留下尽可能大的区间||需求最小的得到的最少)
↓
能确保全局最优(也就是结果正确)
(逻辑自洽:如果我不留下尽可能多的饼干->也就是说新方案饼干减少,其他不变,那么能吃饱的人肯定会不变或减少->非最优方案;如果不留下尽可能大的区间->后面的区间更可能和前面的重叠,需要移除更多->非最优方案)
思路:
首先,顺序问题:先满足最容易满足的(最容易吃饱的/最可能不被剔除的……)
和整体比较:排序–455 435和附近比较(相邻的两个):赋初值+正反遍历两次–135CPP sort?
其次,局部最优:满足&&留下最大余地
最后,按照次序遍历,直至最后(结果已出/遍历完成)
cpp iterate on vector?
例题:
如果觉得《【LeetCode刷题】Greedy贪心算法笔记》对你有帮助,请点赞、收藏,并留下你的观点哦!