Openjudge noi 1.13 13: RMB payment

【 Topic link 】

OpenJudge NOI 1.13 13: RMB payment

【 Topic test site 】

1. Division operation

2. Count array

【 Their thinking 】

This question uses the idea of greed , First, try to take large denomination currency to make a contribution , If you add a currency , The total amount of money is greater than the amount of money to be collected , Then choose a smaller currency to raise money .
Store the face value in the array from large to small a in .

solution 1： Use integer division

Traversal array a, The amount of money that needs to be collected at present is n, The face value concerned is a[i], The number of currencies with this face value is n/a[i], The amount of money left is n%a[i].
Give Way n Into the amount of money left , Look at the next currency with a smaller face value .

solution 2： Use count array

The face value of the current concern is a[i], Take one currency of that face value at a time , Until the denomination currency is used , The amount of money left is less than 0, Then look at the next currency with a smaller face value . Use the count array to record the number of each currency .

【 Solution code 】

solution 1： Use integer division

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    int n, a[6] = {
    100, 50, 20, 10, 5, 1};
    cin >> n;
    for(int i = 0; i < 6; ++i)
    {
    
        cout << n/a[i] << endl;
        n %= a[i];
    }
    return 0; 
}

solution 2： Use count array

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    int n, i = 0, c[6] = {
    }, a[6] = {
    100, 50, 20, 10, 5, 1};
    cin >> n;
    while(n > 0)
    {
    
        if(n >= a[i])// If the rest of the money to be collected is greater than or equal to the current concerned face value 
        {
    
            c[i]++;// The amount of currency with this face value plus 1
            n -= a[i];
        }
        else
            i++;
    }
    for(i = 0; i < 6; ++i)// Output the number of each currency 
        cout << c[i] << endl;
    return 0;
}