问题描述
"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.
问题来自HDU - 3348
输入
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
输出
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".
样例
输入
3
33 6 6 6 6 6
10 10 10 10 10 10
11 0 1 20 20 20
输出
6 9
1 10
-1 -1
思路
这是一道贪心问题,此题有分为两问：
- 求最少纸币时，先从最大金额的开始使用，再去寻找金额小的，直至满足需要金额。
- 求最多纸币时，按照从最小纸币金额开始使用时，贪心就不适用了，因为大金额无法像小金额一样，可以补掉差掉的金额，最后出现的结果会凑不成所需金额。这时可以将思路变一下，各金额纸币数量已给出，所以总金额固定，求满足给定价格的最多纸币数量，就相当于求满足总金额 - 给定价格的最少纸币量，这时便可以用贪心求解，最后用总的纸币数量 - 求得的结果，就得出了最大纸币用量。
AC代码
#include<iostream>
using namespace std;
const int MAXN = 110;
int t;
int arr[MAXN];
int m[] = {0,1,5,10,50,100};
int ans = 0, ans2 = 0;
int money1, money2, count;
int main(){
cin >> t;
while(t--){
ans = 0;
ans2 = 0;
count = 0;
for(int i = 0; i < 6; i++){
cin >> arr[i];
money2 += (m[i] * arr[i]);
count += arr[i];
}
money1 = arr[0];
count = count - money1;
money2 = money2 - money1;
for(int i = 5; i > 0; i--){
int n = money1 / m[i];
int usem = min(n, arr[i]);
money1 -= usem*m[i];
ans += usem;
}
for(int i = 5; i > 0; i--){
int n = money2 / m[i];
int usem = min(n, arr[i]);
money2 -= usem*m[i];
ans2 += usem;
}
if(money1 == 0 && money2 == 0){
cout << ans << " " << count - ans2 << endl;
}else{
cout << -1 << " " << -1<< endl;
}
}
return 0;
}
网友评论