首页 > 试题广场 >

牛牛凑数字

[编程题]牛牛凑数字
  • 热度指数:1317 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛今天逛商店,看到商店里摆着一些很漂亮的数字,牛牛非常喜欢,想买一些数字带回家。
数字一共有九种类型,分别是1-9这九个数字,每个数字的价钱都不一样,而且每个数字的货源都非常充足。
牛牛是个完美主义者,他希望用自己的能够承受的价格,从这些数字里面购买,并且凑到最大的数字带回家。

示例1

输入

5,[5,4,3,2,1,2,3,4,5]

输出

"55555"

说明

第5个数字只需要花费1,所以买5个第5个数字可以凑到最大值55555。
示例2

输入

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类型进行返回。

这个不是个背包问题吗?难道是我理解错了
谁能告诉我这个用例问什么不对呀?
用例输入:30945,[28651,15196,1867,6376,17221,10303,2061,19365,27206]
用例输出:"7777733333333333"
实际输出:"777777777777777"
发表于 2020-08-11 15:10:49 回复(2)
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);
    }

发表于 2020-08-09 00:15:34 回复(0)