☘前言☘
贪心算是很基础的算法了,在这个文章中我们会接触到一些贪心的算法,希望能跟我一起学习呀。。每篇文章后面都有对应的练习题哦,我自己会写题解给大家作为参考,好了不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,大佬们刷完打个卡
大家加油冲!!!!