【题解-Acwing】824. 取现金

题目：824. 取现金

题目描述

艾伦是一个非常富有的人，他在银行存有 n 元钱，现在由于某些私人原因，他要将钱全部取出用于急用。

已知银行的钞票共分 1,5,10,20,100 这 5 种面值。

出于携带方便的考虑，艾伦希望组成这 n 元钱的钞票张数尽可能少。

请问在给定 n 的情况下，组成 n 元钱的钞票张数最少是多少。

输入

共一行，只包含一个整数 n。

输出

共一行，只包含一个整数，表示最少的钞票张数。

数据范围

1

≤

n

≤

10

9

1≤n≤10^9

1≤n≤109

时空范围

1s / 64MB

输入样例

125

输出样例

3

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5+5;
int n,money[N]={1,5,10,20,100},res;
int main(){
cin>>n;
for(int i=4;i>=0;i—){
res+=n/money[i];
n%=money[i];
}
cout<<res;
return 0;
}

结果