如果喜欢大家还希望给个收藏点赞呀0.0
相关知识点大家没基础的还是要看一下的，链接：
《算法笔记知识点记录》第四章——算法初步4——贪心
由于放原题的话文章实在太长，所以题多的话我只放思路和题解，大家请前往相应的网站查看题目呀0.0
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/algorithm-notes
⏳全文大约阅读时间： 30min
全文目录
🍕4.3小节——算法初步->递归
问题 A: 看电视
问题 B: 出租车费
问题 C: To Fill or Not to Fill
问题 D: Repair the Wall
问题 E: FatMouse's Trade
问题 F: 迷瘴
问题 G: 找零钱
B1038 统计同成绩学生 (20 分)
B1020 月饼 (25 分)
1033 To Fill or Not to Fill (25 分)
1037 Magic Coupon (25 分)
1067 Sort with Swap(0, i) (25 分)
1038 Recover the Smallest Number (30 分)
写在最后
🍕4.3小节——算法初步->递归
地址合集：《算法笔记》4.4小节——算法初步->贪心
问题 A: 看电视
其实就是区间贪心的应用，直接拉过来用用就行啦。
#include <stdio.h> #include <algorithm> using namespace std; struct node{ int start; int end; }Node[100]; bool cmp(node a, node b){ if(a.start != b.start) return a.start > b.start; else return a.end < b.end; } int main(){ int m; while(scanf("%d", &m) != EOF && m != 0){ for(int i = 0;i < m;++i) scanf("%d %d", &Node[i].start, &Node[i].end); sort(Node, Node + m,cmp); int ans = 1, last = Node[0].start; for(int i = 1;i < m;++i) if(Node[i].end <= last){ ++ans; last = Node[i].start; } printf("%d\n", ans); } return 0; }
问题 B: 出租车费
我算了一下，13是一个坎，如果等于13可以选择分出来一个8公里，所以思路就是不断的减去8，直到最终的数字小于13。为什么是8呢？因为8公里其实是最低价，为什么是13呢 ，因为8+5的均价刚好是2.4也就是更多的那一段。
#include <cstdio> int main(){ int n; while(scanf("%d", &n) != EOF && n != 0){ double ans = 0; while(n >= 13) n -= 8, ans += 18; if(n < 4) printf("%.0f\n",ans + 10); else if(n <= 8) printf("%.0f\n", ans + 10 + 2*(n-4)); else if(n <= 13) printf("%.1f\n", ans + 10 + 8 + 2.4*(n-8)); } return 0; }
问题 C: To Fill or Not to Fill
这里给了提示，我们就按照他给的方式，先判断能不能跑到最后，然后中间进行区间贪心，硬贪。
#include <cstdio> #include <algorithm> using namespace std; struct Sta{ double price; double distance; }sta[500]; //加油站的数据结构 bool cmp(Sta a, Sta b){ return a.distance < b.distance; } int main(){ double cmax, d, davg; int n; scanf("%lf %lf %lf %d",&cmax, &d, &davg, &n); //读入总信息 for(int i = 0;i < n; ++i) scanf("%lf %lf", &sta[i].price, &sta[i].distance); //读入数据 sort(sta,sta + n, cmp); //跑不完全程的处理 double maxdistance = -1, minprice = 0; for(int i = 0;i < n - 1; ++i) if(sta[i + 1].distance - sta[i].distance > cmax * davg) {maxdistance = sta[i].distance + cmax * davg; break;}//中间某个炸了 if(sta[0].distance != 0) maxdistance = 0.00; //一开始就没加油站 else if(maxdistance == -1 && d - sta[n - 1].distance > cmax * davg) maxdistance = sta[n-1].distance + cmax * davg; //最后一个加油站跑不到 if(maxdistance != -1) {printf("The maximum travel distance = %.2f\n",maxdistance);return 0; } //输出就好了 double dis = cmax * davg, curdistance = 0; for(int i = 0;i < n && curdistance < d; ++i){ int j; for(j = i + 1; j < n && sta[j].distance - sta[i].distance <= dis;++j) if(sta[j].price < sta[i].price) break; if(j < n && sta[j].distance - sta[i].distance <= dis) //有更便宜的加油站 if(curdistance >= sta[j].distance) continue; //能跑到便宜加油站 跑就完事了 else minprice += (sta[j].distance - curdistance) / davg * sta[i].price, curdistance = sta[j].distance; //不能 加点油跑到 else //没有更便宜的加油站 if(d - sta[i].distance <= dis) minprice += (d - curdistance) /davg * sta[i].price,curdistance = d; //直接干到底了 else minprice += (sta[i].distance - curdistance + dis) / davg * sta[i].price, curdistance = sta[i].distance + dis; //加满 } printf("%.2f\n",minprice); return 0; }
问题 D: Repair the Wall
直接贪心选择最大的就好了。
#include <cstdio> #include <algorithm> using namespace std; bool cmp(int a, int b){ return a >b; } int main(){ int l, n; while(scanf("%d %d", &l, &n) != EOF){ int a[n]; for(int i = 0;i < n;++i) scanf("%d", a + i); sort(a, a+n, cmp); int count = 0; for(int i = 0;i < n;++i){ if(l <= 0) break; l -= a[i]; ++count; } if(l <= 0) printf("%d\n",count); else printf("impossible\n"); } return 0; }
问题 E: FatMouse’s Trade
每次选择性价比最高的就行了
#include <cstdio> #include <algorithm> using namespace std; struct node{ double J,F; }Node[1010]; bool cmp(node a, node b){ return a.J/a.F > b.J/b.F; } int main(){ double M; int N; while(scanf("%lf %d", &M, &N) != EOF && (M != -1 && N != -1)){ for(int i = 0;i < N; ++i) scanf("%lf %lf",&Node[i].J, &Node[i].F); sort(Node, Node + N, cmp); int now = 0; double max = 0; while(M != 0 && now < N){ if(M <= Node[now].F){ max += Node[now].J /Node[now].F * M; break; } max += Node[now].J; M-= Node[now].F; now++; } printf("%.3f\n",max); } return 0; }
问题 F: 迷瘴
#include <cstdio> #include <algorithm> using namespace std; int main(){ int c; scanf("%d",&c); while(c--){ int n, v, w; scanf("%d %d %d", &n, &v, &w); int p[n]; for(int i = 0;i < n;++i) scanf("%d",p + i);//读入数据 sort(p, p + n); //从小到大排序 int ansv = 0,now = 0;double answ = 0; while(now < n && (ansv * answ + v * p[now]) / (ansv + v) <= w){ answ = (ansv * answ + v * p[now]) / (ansv + v); ++now; ansv += v; } printf("%d %.2f\n",ansv,answ/100.0); } }
问题 G: 找零钱
#include <cstdio> #include <algorithm> using namespace std; int num[5] = {50,20,10,5,1}; int main(){ int n; while(scanf("%d",&n) != EOF){ int now = 0; while(n){ int tmp = 0; while(now < 5 && n < num[now]) ++now; while(now < 5 && n >= num[now]) ++tmp, n-= num[now];//找零钱 printf("%d*%d",num[now],tmp); if(n) printf("+"); } puts(""); } return 0; }
B1038 统计同成绩学生 (20 分)
地址:B 1023 组个最小数 (20 分))
例题。。。。
#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; }
B1020 月饼 (25 分)
地址：B1020 月饼 (25 分)|A1070 Mooncake (25 分)
例题。。。。
#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; }
1033 To Fill or Not to Fill (25 分)
地址：1033 To Fill or Not to Fill (25 分)
上面写过啦
#include <cstdio> #include <algorithm> using namespace std; struct Sta{ double price; double distance; }sta[500]; //加油站的数据结构 bool cmp(Sta a, Sta b){ return a.distance < b.distance; } int main(){ double cmax, d, davg; int n; scanf("%lf %lf %lf %d",&cmax, &d, &davg, &n); //读入总信息 for(int i = 0;i < n; ++i) scanf("%lf %lf", &sta[i].price, &sta[i].distance); //读入数据 sort(sta,sta + n, cmp); //跑不完全程的处理 double maxdistance = -1, minprice = 0; for(int i = 0;i < n - 1; ++i) if(sta[i + 1].distance - sta[i].distance > cmax * davg) {maxdistance = sta[i].distance + cmax * davg; break;}//中间某个炸了 if(sta[0].distance != 0) maxdistance = 0.00; //一开始就没加油站 else if(maxdistance == -1 && d - sta[n - 1].distance > cmax * davg) maxdistance = sta[n-1].distance + cmax * davg; //最后一个加油站跑不到 if(maxdistance != -1) {printf("The maximum travel distance = %.2f\n",maxdistance);return 0; } //输出就好了 double dis = cmax * davg, curdistance = 0; for(int i = 0;i < n && curdistance < d; ++i){ int j; for(j = i + 1; j < n && sta[j].distance - sta[i].distance <= dis;++j) if(sta[j].price < sta[i].price) break; if(j < n && sta[j].distance - sta[i].distance <= dis) //有更便宜的加油站 if(curdistance >= sta[j].distance) continue; //能跑到便宜加油站 跑就完事了 else minprice += (sta[j].distance - curdistance) / davg * sta[i].price, curdistance = sta[j].distance; //不能 加点油跑到 else //没有更便宜的加油站 if(d - sta[i].distance <= dis) minprice += (d - curdistance) /davg * sta[i].price,curdistance = d; //直接干到底了 else minprice += (sta[i].distance - curdistance + dis) / davg * sta[i].price, curdistance = sta[i].distance + dis; //加满 } printf("%.2f\n",minprice); return 0; }
1037 Magic Coupon (25 分)
地址：1037 Magic Coupon (25 分)
思路：先排序，然后贪就完事了，但是需要注意的是第三个测试点是两个数组长度是不同的，所以再从后往前进行负数的计算的时候，需要声明两个变量，否则就像我一样卡半天。
#include <cstdio> #include <algorithm> using namespace std; bool cmp(int a, int b){ return a > b; } int coupons[100010], product[100010]; int main(){ int n, m; scanf("%d", &n); for(int i = 0;i < n;++i) scanf("%d", coupons + i); scanf("%d", &m); for(int i = 0;i < m;++i) scanf("%d", product + i); sort(coupons , coupons + n, cmp); //从大到小排列 sort(product, product + m, cmp); //从大大小排列 int ans = 0; for(int i = 0; i < m && i < n && coupons[i] > 0 && product[i] > 0;i++) ans += coupons[i] * product[i]; //从前往后正数最大 for(int i = n - 1, j = m - 1; i >= 0 && j >= 0&& coupons[i] < 0 && product[j] < 0;--i,--j) ans += coupons[i] * product[j];//从后往前 负数最大 printf("%d",ans); }
1067 Sort with Swap(0, i) (25 分)
地址：1067 Sort with Swap(0, i) (25 分)
思路：模拟整个过程，先努力将第一个位置的元素换到正确，然后接下来如果有位不对 就将当前位与其他位努力交换到正确，因为不是0号位置，所以非0号位的交换实际的过程是先将元素换到0号位，换到正确再和0号位换回来所以多了两次交换。贪 硬贪。
#include<cstdio> int num[100009]; void swap(int *a , int *b){ *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } int main(){ int n ; scanf("%d", &n); //读入n for(int i = 0;i < n;++i) scanf("%d", num + i);// 读入所有数据 int count = 0; for(int i = 0;i < n;++i){ if(i != 0 && i != num[i]) count += 2; while(num[i] != i) swap(num + i, num + num[i]),++count; //模拟过程 //printf("%d %d\n",i,count); } printf("%d\n" , count); }
1038 Recover the Smallest Number (30 分)
地址：1038 Recover the Smallest Number (30 分)
思路：先排序，然后根据排序的结果每次选择连接之后生成串较小的。排序的时候不能使用cmp直接比较，而是先将两个串拼接一下，看看怎么拼比较小。
另外,直接生成一个二维数组的话无法修改两个指针的值，所以需要使用动态申请
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> using namespace std; bool cmp(char *s1, char *s2){ char tmp1[20],tmp2[20]; strcpy(tmp1, s1);strcpy(tmp2,s2);strcat(tmp1,s2);strcat(tmp2,s1); return strcmp(tmp1, tmp2) < 0; } int main(){ int n; scanf("%d",&n); char *tmp[n]; for(int i = 0;i < n;++i){ tmp[i] = (char *)malloc(sizeof(char) * 10); scanf("%s", tmp[i]); if(strlen(tmp[i]) == 0) --i,--n,free(tmp[i]); } sort(tmp, tmp + n,cmp); //从小到大排列 int flag = true; for(int i = 0;i < n;++i){ int size = strlen(tmp[i]); for(int j = 0;j < size;++j) if(flag && tmp[i][j] == '0') continue; else putchar(tmp[i][j]), flag = false; } if(flag) printf("0\n"); else puts(""); return 0; }
写在最后
贪心好难，，，，我被加油站差点干废，所以托更了，对不住。。。我尽量更，我不是鸽子精。。。大家根据习题练习一下会有一种打通任督二脉的感觉，虽然过程艰难，但是结果一定是好的！！！
