结构体,sort(贪心算法)洛谷每日一题(洛谷P2240)
2022/1/7 14:04:19
本文主要是介绍结构体,sort(贪心算法)洛谷每日一题(洛谷P2240),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
一、前言
二、题目描述
三、题目解读
四、完整代码
五、细节解读
六、AC凭证
七、水话
一、前言
因为昨天有聊到如何使用c++里面的sort函数,并且着重介绍了sort与结构体的结合解决一些贪心的算法题目,那不就来了嘛,为了让一些读者有更好的连续性,所以今天这一题就是介绍结构体和sort的联合使用的妙处,这题是一个部分背包问题,那么相信很多熟悉DP问题的读者,肯定会想到背包问题肯定就是一个dp动态规划嘛,要找一些dp数组,但是此题如果利用动态规划去做的话,会有很多的问题甚至是做不出来的,大家可以体会一下!!前文的链接(sort函数讲解)
二、题目描述
三、题目解读
其实题目大家都看得懂,所以主要想介绍一下,这里的贪心思想。我们可以看到藏宝洞里面的N堆藏金币,然后每一堆的金币有相应的价格,然而题目说到了所有的金币都是可以随意分割的,这个大家必须好好理解,也就是说,假设你背包只剩下5kg的重量可以装了,都是剩余的金币,每一堆金币的重量都大于5kg,如果按照背包的基本动态规划来想的话,是没有办法继续加上任何一堆金币的价格的,但是本题不同点就在,我可以只拿其中金币的一堆的5kg然后得到它对应的价格哦!那么这个时候的贪心思想是什么呢?我们一定会拿1单位价格/kg最高的那一堆金币,也就是v/m(m表示总质量,v表示总价格)最大的那一堆,那么按照这一个思想,从一开始,就让所有堆的金币按照v/m从大到小排序,然后依次进行贪心的拿取,那么到最后一定能得到最大的钱!!当然,这样,聪明的你就可以发家致富了哈哈哈哈!
四、完整代码
#include <bits/stdc++.h> using namespace std; struct node { int m; //每一堆的总质量 int v; //每一堆的总价格 }; node a[105]; bool com(node aa,node bb) { return aa.v*bb.m>aa.m*bb.v; //这个写法避免浮点数精度的影响,就是移项 } int main() { double ans=0; int N,T; cin>>N>>T; for(int i=1;i<=N;i++) { cin>>a[i].m>>a[i].v; } sort(a+1,a+N+1,com); //因为下标是从1开始,所以sort的前后都加一个1就好了 for(int i=1;i<=N;i++) { if(T>=a[i].m) //能够拿全,就全部拿下 { ans+=a[i].v; T-=a[i].m; } else { ans=ans+T*(double(a[i].v)/double(a[i].m)); //如果拿不全就能拿多少拿多少 break; } } printf("%.2lf",ans); //按照题目要求进行输出 }
五、细节解读
①com函数里面的写法:其实想表示v1/m1>v2/m2,但是按照本蒟蒻的代码来看,移项之后再进行一个比较,其实是能够避免一些因为精度问题比较上的失误,这个写法以后大家在遇到类似的题目也会有相应的经验的!
②if-else:主函数的这一处判断正是和背包问题的不同地方,遵循能拿就拿的原则,且拿的顺序已经被固定,相当于每一次的判断拿取,都是在拿一个最优解。贪心的思想就是每一个子问题都拿到了最优解,那么最终的答案也一定会是最优解!
六、AC凭证
七、水话
从上面的题目我们可以看出,结构体结合sort是有多么的便捷,而且大家在判断一个题目是什么算法的时候,一个不能仅仅因为题目来判定,一定要仔细的读题,然后找到这个题目隐藏的条件,好好判断该利用什么思路解题。比如这题如果刚开始就去想动态规划,一定会浪费很多的时间去纠正这一个错误的思想的!啊啊啊啊每日一水题解写完了,下午要考线代,祝我加油鸭!
这篇关于结构体,sort(贪心算法)洛谷每日一题(洛谷P2240)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)