牛牛今天逛商店,看到商店里摆着一些很漂亮的数字,牛牛非常喜欢,想买一些数字带回家。
数字一共有九种类型,分别是1-9这九个数字,每个数字的价钱都不一样,而且每个数字的货源都非常充足。
牛牛是个完美主义者,他希望用自己的能够承受的价格,从这些数字里面购买,并且凑到最大的数字带回家。
5,[5,4,3,2,1,2,3,4,5]
"55555"
第5个数字只需要花费1,所以买5个第5个数字可以凑到最大值55555。
2,[9,11,1,12,5,8,9,10,6]
"33"
购买2个第3个数字,可以凑到最大值为33。
第一个参数为一个整数n(0 ≤ n ≤ 106),代表牛牛所能承受的价格。第二个参数为1-9这九个数字的价格数组,a1,a2,……,a9(1≤ ai ≤105)。程序应返回:一个数字,代表牛牛能凑到的最大的数字。当然,如果牛牛一个数字都买不起,返回"-1"即可。注意,由于数字可能会很大,所以程序中需要处理成string类型进行返回。
public String solve (int n, int[] a) { // write code here StringBuffer sb = new StringBuffer(); int max = 0 ,temp; for(int i = 0; i<a.length;i++){ //位数越多值越大,相同位数 数字越大值越大 temp=n/a[i]*10+i; if(temp>max){max=temp;} } //买不起返回"-1" int times = max/10; //位数 if(times<=0){return "-1";} //进行组装 int num = max%10+1; //数字 for (int i = 0; i <times ; i++) { sb.append(num); } //判断当前数字价格+剩余的钱能否买一个更大的数 temp=num-1;//还原数字下标 for(int i = num,money=a[temp]+n%a[temp]; i < 9 ; i++){ if(a[i]<=money && i > temp){ temp = i; } } //如果能换,进行下一步判断,否则输出 if(temp>=num) { //判断剩余的钱能换几个当前数字 for (int i = 2, price = a[temp] - a[num - 1], money = n % a[num - 1]; i <= times; i++) { if (price * i > money) { times = i-1; break; } } //进行替换并返回字符串 String s = temp+1+""; for(int i=0;i<times;i++) { sb.replace(i, i + 1, s); } } return sb.substring(0); }