餐饮网站建设网站,企业网站包含哪些页面,营销培训课程视频,h5响应式网站源码一#xff1a;题目
设有6 种不同面值的硬币#xff0c;各硬币的面值分别为5 分#xff0c;1 角#xff0c;2 角#xff0c;5 角#xff0c;1 元#xff0c;2元。现要用这些面值的硬币来购物。在购物中希望使用最少个数硬币。例如#xff0c;1 次购物需要付款0.55 元题目
设有6 种不同面值的硬币各硬币的面值分别为5 分1 角2 角5 角1 元2元。现要用这些面值的硬币来购物。在购物中希望使用最少个数硬币。例如1 次购物需要付款0.55 元如果没有5 角的硬币只好用22角11角1*5分 共4 枚硬币来付款。
对于给定的各种面值的硬币个数和付款金额计算使用硬币个数最少的交易方案。
输入格式: 输入数据有若干组第一行给出一个整数n表示输入数据的组数。
以下n行每一行有6 个整数和1个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。
输出格式: 输出每组数据的最少硬币个数。如果不可能完成交易则输出“impossible”。
输入样例:
2
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55输出样例:
4
4二思路
思路 1.map容器进行存储 键值为面值0.050.10.20.512 关键值为对应的硬币个数 2.将付款金额跟面值进行比较找到刚好大于其面值的银币并判断其个数是否有无, 1:如果其个数为0就继续往下寻找银币直到银币个数不为0为止 2:如果其个数不为0的话那么我们就选择 小于 付款金额的 银币数 并记录个数 付款金额 付款金额 - 面值*银币数;
当付款金额小于面值的时候继续往下寻找更小的面值 当银币数不够了也是往下继续寻找最小隐蔽数
3.如果最后的付款金额不为0,那么就是 impossible
测试数据:2 2 4 2 2 1 0 0.95 2 4 2 0 1 0 0.55
4.注意处理数据中的小数问题因为double 存的数据和真实的并不一样 eg :比如存入的是0.95 其实是0.9499999999182那么当数据剩下0.0499909 那么它和0.05就无法比较了
三关于处理double类型数据的精度问题
1.问题展示
问题描述我们明明输入的是double类型的 0.95 但通过调试我们发现其实他是 0.949999999
2.回归本题
本题但这中的测试用例1中有0.95这个付款金额那么我们选择银币的时候会选择一个 0.5两个0.2那么还剩0.05, 剩下0.05是我们希望的正常情况但是通过上方的演示我们发现其是真实的值是小于0.05的那么这样的话就会影响我们计算银币的个数因为统计不到0.05的银币个数
3.解决问题
本题当中自我感觉很开窍的地方我们给付款金额加上0.00001这样就能保证我的数据最起码是大于面值的最后的余额再跟0.00001比较如果小于其就是可以完全换成金币个数的。注意这里不能是等于0.00001因为确实是两个数不相等而且即便你将调试显示的数抄上去都不行
四上码 /**思路1.map容器进行存储 键值为面值0.050.10.20.512 关键值为对应的硬币个数2.将付款金额跟面值进行比较找到刚好大于其面值的银币并判断其个数是否有无,1:如果其个数为0就继续往下寻找银币直到银币个数不为0为止2:如果其个数不为0的话那么我们就选择 小于 付款金额的 银币数 并记录个数 付款金额 付款金额 - 面值*银币数;当付款金额小于面值的时候继续往下寻找更小的面值当银币数不够了也是往下继续寻找最小隐蔽数3.如果最后的付款金额不为0,那么就是 impossible 测试数据:22 4 2 2 1 0 0.952 4 2 0 1 0 0.55 4.注意处理数据中的小数问题因为double 存的数据和真实的并不一样eg :比如存入的是0.95 其实是0.9499999999182那么当数据剩下0.0499909那么它和0.05就无法比较了 */#includebits/stdc.husing namespace std;int res(vectordouble v){mapdouble,doublem;mapdouble,double:: reverse_iterator t;int length v.size();float pay 0.00001; //付款金额 int cnt 0;//统计银币个数 for(int i length - 1; i 0; i--){if(i 0) m[0.05] v[i];if(i 1) m[0.1] v[i];if(i 2) m[0.2] v[i];if(i 3) m[0.5] v[i];if(i 4) m[1] v[i];if(i 5) m[2] v[i]; if(i 6) pay v[i];}for(t m.rbegin(); t ! m.rend(); t){if(pay t-first t-second ! 0){//如果付款金额大于其面值 并且该面值银币数不为0 for(int i 0; i t-second; i){if(pay t-first){//这里确保每次的付款金额均大于面值 pay pay - t-first;cnt; }else{break;}}} }//cout cnt;// cout pay endl;//0.00999999139 if(pay 0.001){return cnt;// cout wyj;}return -1; }int main(){int n;cin n;for(int i 0; i n; i){vectordoublev;for(int i 0; i 7; i){double nums;cin nums;v.push_back(nums);}int ans res(v);if(ans -1){cout impossible endl;}else{cout ans endl;}} } //2//2 4 2 2 1 0 0.95//2 4 2 0 1 0 0.55//////1//2 4 2 2 1 0 0.95//1//2 4 2 2 1 0 0.05////1//2 4 2 2 1 0 0.95 五知识速递如果对map容器不熟悉的兄弟们可以了解下
map的逆序遍历 map的基本用法
又得唠叨一句 记得加油 宝!!
