題目鏈接
題目描述
作為杭電的老師，最盼望的日子就是每月的8號了，因為這一天是發工資的日子，養家糊口就靠它了，呵呵
但是對于學校財務處的作業人員來說，這一天則是很忙碌的一天，財務處的小胡老師最近就在考慮一個問題：如果每個老師的工資額都知道，最少需要準備多少張人民幣，才能在給每位老師發工資的時候都不用老師找零呢？
這里假設老師的工資都是正整數，單位元，人民幣一共有100元、50元、10元、5元、2元和1元六種，
Input
輸入資料包含多個測驗實體，每個測驗實體的第一行是一個整數n（n<100），表示老師的人數，然后是n個老師的工資，
n=0表示輸入的結束，不做處理，
Output
對于每個測驗實體輸出一個整數x,表示至少需要準備的人民幣張數，每個輸出占一行，
Sample Input
3
1 2 3
0
Sample Output
4
思路
貪心思想，在發工資的時候，能給面值100元的，就不給面值1元的，因為這樣可以準備更少量的人民幣，因此如果想要最少張數的人民幣，又規定不找零，就需要盡可能的準備大面額的人民幣，
C++代碼：
#include<bits/stdc++.h>
using namespace std;
int num[105];
int main()
{
ios::sync_with_stdio(false);
int n;
while(cin >> n)
{
if(n == 0) break;
int count = 0;
for(int i = 0; i < n; i++)
cin >> num[i];
for(int i = 0; i < n; i++)
{
count += num[i] / 100;
num[i] %= 100;
if(num[i] >= 50) {count++; num[i] -= 50;}
while(num[i] >= 10) {count++; num[i] -= 10;}
if(num[i] >= 5) {count++; num[i] -= 5;}
while(num[i] >= 2) {count++; num[i] -= 2;}
if(num[i] == 1) count++;
}
cout << count << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/254087.html
標籤：其他
上一篇：android組件化