/**
 * 题目描述：
 * 第一题：人民币分为（1,5,10,20,50,100）的金额，若交易金额为19，收银（50），找零（20+10+1）交易所需人民币张数为4.
 * 或者收银（10+5+1+1+1+1）交易所需人民币张数为6.输入交易金额n,输出交易所需最少人民币数量
 * @author young
 *
 */
public class MoneyNumberLeast 
{
	
	private static int[] moneyArrays = {100, 50, 20, 10, 5, 1};
		
	private static int[] moneyNumber = new int[100];
	
	
	static
	{
		//初始化获得1-99交易额的最少人民币数量
		for(int i = 1; i < 100; i ++)
		{
			moneyNumber[i] = getMinNumberOfMoney(i);			
		}
	}
	
	/**
	 * n元进行分解，最少需要的人民币的数量
	 * @param n
	 * @return
	 */
	public static int getMoneyNumber(int n)
	{
		int sum = 0;
		for(int i = 0; i < moneyArrays.length; i ++)
		{
			int number = n / moneyArrays[i];
			sum += number;
			
			n = n % moneyArrays[i];
		}
		return sum;
	}
	
	
	/**
	 * 输入金额为n,返回最少的人民币数量
	 * @param n在1-99之间
	 * @return
	 */
	public static int getMinNumberOfMoney(int n)
	{
		if(n < 1 || n > 99) return -1;
		
		//第一种情况：直接支付不找零
		int  sum1 = getMoneyNumber(n);
		
		
		
		//第二种情况，支付，找零		
		int i = moneyArrays.length - 1;
		while(n / moneyArrays[i] != 0)
		{
			i--;
		}
		
		int sum2 = getMoneyNumber(moneyArrays[i] - n) + 1;			
		return Math.min(sum1, sum2);
	}
	
	
	public static int getMinNumber(int n)
	{
		
		//100以内的人民币数量
		int numberother = 0;
		//100元的人民币数量
		int number100 = n / 100;
		n = n % 100;
		if(n > 0)
		{
			numberother = moneyNumber[n];
		}
		
		return number100 + numberother;
	}	
}