HDU 3348 coins【贪心】

题目来戳呀

Problem Description

“Yakexi, this is the best age!” Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao) “Thanks to the best age, I can buy many things!” Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn’t like to get the change, that is, he will give the bookseller exactly P Jiao.

Input

T(T<=100) in the first line, indicating the case number. T lines with 6 integers each: P a1 a5 a10 a50 a100 ai means number of i-Jiao banknotes. All integers are smaller than 1000000.

Output

Two integers A,B for each case, A is the fewest number of banknotes to buy the book exactly, and B is the largest number to buy exactly.If Dong MW can’t buy the book with no change, output “-1 -1”.

Sample Input

3 33 6 6 6 6 6 10 10 10 10 10 10 11 0 1 20 20 20

Sample Output 6 9 1 10 -1 -1 题意： 换零钱。求钱数能换的最多张数和最小张数。 想法一： 贪心啊摔！以为是动态规划啊摔！马丹分不清啊当时！（上篇博客搞懂了QAQ） 最少可以直接用贪心，最多的话，要用小的面值替换大的面值。 但用小的来补时，需要先找到满足条件的最小纸币总数对应的i值。（←不是很理解）

下面这是某猪的代码，强迫症表示很满足0v0

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std; int a[5], b[5];//1 5 10 50 100 int main() { int t, p, ans1, ans2;; scanf("%d",&t); while(t--) { scanf("%d",&p); ans1 = ans2 = 0; for(int i = 0; i < 5; ++i) scanf("%d",&a[i]); for(int i = 0; i < 5; ++i) b[i] = a[i]; int tem = p; while(tem >= 100 && a[4]) { tem -= 100; a[4]--; ans2++; } while(tem >= 50 && a[3]) { tem -= 50; a[3]--; ans2++; } while(tem >= 10 && a[2]) { tem -= 10; a[2]--; ans2++; } while(tem >= 5 && a[1]) { tem -= 5; a[1]--; ans2++; } while(tem >= 1 && a[0]) { tem -= 1; a[0]--; ans2++; } if(tem > 0) {//说明零钱不够找不开了 cout << "-1 -1" << endl; } else {//tem=0纸币最少能够正好找开时 while(b[0] + b[1] * 5 + b[2] * 10 + b[3] * 50 < p) { p -= 100; ans1++; } while(b[0] + b[1] * 5 + b[2] * 10 < p) { p -= 50; ans1++; } while(b[0] + b[1] * 5 < p) { p -= 10; ans1++; } while(b[0] < p) { p -= 5; ans1++; } ans1 += p; cout << ans2 << " " << ans1 << endl; } } return 0; }

想法二： 既然最小的可以直接贪心，那我们用总张数—某一部分的最少不就是最多了吗！这一部分就是给的纸币张数的总金额—题目要求的金额p。 代码来自空有想法的我没有实现哭哭 这份贪心求最小的和上面的那份不一样，简洁但是不够暴力hhh 但是中心思想都是一样的！

#include <cstdio> #include <cstring> int b[10]={0,1,5,10,50,100}; int main() { int t; int p,r; int a[10],c[10],e[10]; int i,j,k,sum; scanf("%d",&t); while(t--) { sum=0; scanf("%d",&p);//要求的金额 r=p; for(i=1;i<=5;i++) { scanf("%d",&a[i]);//张数 sum+=b[i]*a[i];//总金额 } for(i=5;i>0;i--) { if(r/b[i]<a[i]) { c[i]=r/b[i];//从大往下存张数到c数组中 r=r-b[i]*c[i];//给定金额一轮循环后剩下的钱 } else { c[i]=a[i];//当大张数不够时，只能把所有大的都加起来了啊 r=r-c[i]*b[i]; } } if(r!=0) { printf("-1 -1\n"); } else {//以下就是求另一部分的最小啊 k=sum-p; for(i=5;i>0;i--) {//是从最大的往下找 if(k/b[i]<a[i]) { e[i]=k/b[i]; k=k-b[i]*e[i]; } else { e[i]=a[i]; k=k-e[i]*b[i]; } } if(k==0) { printf("%d %d\n",c[1]+c[2]+c[3]+c[4]+c[5],(a[1]+a[2]+a[3]+a[4]+a[5]-(e[1]+e[2]+e[3]+e[4]+e[5]))); } } } }