[贪心]coins（贪心经典例题）

问题描述

"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;
}