“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
求最少数量时，直接用贪心算法，求最大数量时，直接用求最小数量的函数，带入 所有的钱-需要花的钱，求出最少的数量，然后再用所有纸币的数量减去它就可以了。。。。。
#include<iostream> #include<cstdio> using namespace std; #define N 5 int num[10];//纸币数量 int value[10]={1,5,10,50,100};//纸币价值 int mi(int a,int b) { if(a<b) return a; else return b; } int minn(int n)//求最细小数量（贪心） { int ans=0; for(int i=N-1;i>=0;i--) { int c; c=mi((n/value[i]),num[i]); n=n-c*value[i]; ans+=c; } if(n!=0) ans=-1; return ans; } int main() { int T,p; cin>>T; while(T--) { int l=0,ll=0; cin>>p; for(int i=0;i<5;i++) { cin>>num[i]; l+=num[i];//所有纸币之和 ll+=num[i]*value[i];//钱的总数 } if(p>ll)//如果所需要的钱大于拥有的钱，就直接结束好啦 { cout<<"-1"<<' '<<"-1"<<endl; continue; } int tt=minn(p),tttt; if(minn(ll-p)==-1) tttt=-1; else tttt=l-minn(ll-p); cout<<tt<<' ';//最少数量 cout<<tttt<<endl;//最多数量 } return 0; }