☘前言☘
贪心算是很基础的算法了，在这个文章中我们会接触到一些贪心的算法，希望能跟我一起学习呀。。每篇文章后面都有对应的练习题哦，我自己会写题解给大家作为参考，好了不bb了，我们开始把！
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/algorithm-notes
⏳全文大约阅读时间： 120min(有点长，大家忍一下 ，一定会有蜕变的)
简单贪心
贪心法是求解最优化问题的一种方法，考虑的是时时刻刻都是局部最优解，从而最终得到全局最优解的方法。一般来说贪心的证明非常复杂，所以一道题看着像贪心，并且我们无法找到反例推翻贪心的时候就应该大胆的使用它。
PAT B1020月饼
上面的介绍都很模糊，你可能不太能看懂，那我们就直接看一道题，你肯定马上就懂了。
B1020 月饼 (25 分)
题目描述
给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。销售时允许取出一部分库存。
输入样例
3 20
18 15 10
75 72 45
输出样例
94.50
解题思路
其实很容易想到吧，计算一下每个月饼的单价，每次都选择最贵的进行销售，最终得到的收益一定可以使最终的收益最大。有了思路，代码就很容易了。
#include <cstdio> #include <algorithm> using namespace std; struct yuebing{ double kucun; double shoujia; double danjia; }yue[1009]; bool cmp(yuebing a, yuebing b){ return a.danjia > b.danjia; //为了贪心排序 } int main(){ int n; double d; scanf("%d %lf", &n, &d); for(int i = 0;i < n;++i) scanf("%lf",&yue[i].kucun); for(int i = 0;i < n;++i){ scanf("%lf",&yue[i].shoujia); yue[i].danjia = yue[i].shoujia / yue[i].kucun;//直接计算 } sort(yue, yue + n, cmp); double ans = 0; for(int i = 0;i < n;++i) if(d > yue[i].kucun) ans += yue[i].shoujia, d -= yue[i].kucun; else { //不够了 只卖需要的库存 ans += yue[i].danjia * d; break; } printf("%.2lf\n",ans); return 0; }
需要注意的坑：
库存和总售价都是正数。所以可能是小数，所以用double。
虽然总需求量是正整数，但是总监计算的时候会减，可能会出问题，所以直接用double省心。
B 1023 组个最小数 (20 分)
B 1023 组个最小数 (20 分))
题目描述
给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。
现给定数字，请编写程序输出能够组成的最小的数。
输入样例
2 2 0 0 0 3 0 0 1 0
输出样例
10015558
解题思路
其实很简单，就是第一位选择非0的最小值，后面依次打印出最小值就好了。
#include <cstdio> int main(){ int hash[10] = {0}; int tmp; for(int i = 0;i < 10;++i) scanf("%d",&tmp),hash[i] = tmp; for(int i = 1;i < 10;++i) //第一位 if(hash[i]){ printf("%d",i); --hash[i]; break; } for(int i = 0;i < 10;++i) while(hash[i]){ printf("%d",i); --hash[i]; } puts("");//最后的回车 return 0; }
区间贪心
给一个例子：435. 无重叠区间
问题的问题是怎么取出最少的区间使最终的区间不重叠。那么其实它的类似问题是怎么选出尽可能多的不重叠区间，这就是区间贪心的应用之处。
对于第一种情况，显然我们需要选择包含长度小的 也就是I1
对于第二种情况，我们将左端点从大到小排列我们可以发现
如果去掉右边的一部分 左边的部分总是被I2包含，同理可以得到I3
和I1也是一样的道理，我们选择I1 最好。也就是每次我们都选择左端点最大的区间。
所以我们就是将左端点从大到小排列，如果相同则按照右端点从小到大（对应第一种情况），然后每次选择左端点最大的区间，如果下一个区间与选中区间不重叠就新增一个区间就好了。
代码如下：
struct node{ int x; int y; }Node[100009]; int cmp(struct node *a,struct node *b){ if(a->x != b->x) return a->x > b->x ? -1 : 1; else return a->y < b->y ? -1 : 1; } int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){ for(int i = 0;i < intervalsSize;++i) Node[i].x = intervals[i][0],Node[i].y = intervals[i][1]; qsort(Node,intervalsSize,sizeof(struct node),cmp); int ans = 1, last = Node[0].x; for(int i = 1;i < intervalsSize;++i) if(Node[i].y <= last){ last = Node[i].x; ans++; } return intervalsSize - ans; }
时间复杂度还行，因为利用了新的节点，所以空间比不过。文章里用力扣是为了表现思想，大家平时刷题还是多用OJ，在力扣的代码很不规范，习惯不好，大家加油！
推荐专栏
🍭《算法笔记》记录🍭
👻算法笔记刷题👻
🐳课后习题
我写完会放题解，大家写完了可以在评论区打卡哟！题解我放评论区吧，这样不用修改文章。
题解：评论区见，置顶没有就是我没写完0.0，大佬们刷完打个卡
大家加油冲！！！！
