【牛客编程巅峰赛S1第4场】牛牛凑数字

题目

数字一共有九种类型，分别是 1 - 9 这九个数字，每个数字的价钱都不一样，而且每个数字的货源都非常充足。
在能够承受的价格内，从这些数字里面购买，并且凑到最大的数。

解题思路

要凑成最大的数，

1. 先求出最大的位数：遍历价格，求出最低的价格 a[minIndex]，则最大的位数为 k = n / a[minIndex]。
2. 再者，高位上的数字越大，数越大：如果钱有剩余，可以购买更大的数字，替换掉原来的数字，从高位开始替换。

C++代码

class Solution {
public:
    /**
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型vector 1-9这九个数字的价格数组
     * @return string字符串
     */
    string solve(int n, vector<int>& a) {
        // write code here
        int minIndex = 8;
        for(int i=7; i>=0; --i){
            if(a[i] < a[minIndex]){
                minIndex = i;
            }
        }
        if(n < a[minIndex])
            return "-1";

        int k = n / a[minIndex];
        char c = '1' + minIndex;
        string ans(k, c);

        int d = n % a[minIndex];
        if(d == 0)
            return ans;

        int j = 0;
        for(int i=8; i>minIndex; --i){
            while(a[i] <= a[minIndex] + d){
                ans[j] = '1' + i;
                d -= a[i]-a[minIndex];
                ++j;
            }
            if(d==0)
                break;
        }

        return ans;
    }
};