题解 | #牛牛凑数字#

题意

牛牛拥有一定数量的钱，而1-9的数字分别有价格，请问牛牛能用这些钱买到的数字组合起来最大是多少？

方法一(暴力求解)

考虑暴力枚举。依次从低位开始，买下某个数字并填上去。当没有钱买数字时，返回最终的数字。比较后得出最大答案。

class Solution {
public:
    bool cmp (string &a,string &b) {
        if (a.length() != b.length()) {
            return a.length() > b.length();
        }
        for (int i = 0;i < a.length();++ i) {
            if (a [i] != b [i]) {
                return a [i] > b [i];
            }
        }
        return false;    //相等 
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型vector 1-9这九个数字的价格数组
     * @return string字符串
     */
    string buyNumber(int n, vector<int>& a) {
        bool noAns = true;
        for (int i = 0;i < 9;++ i) {
            if (a [i] <= n) {
                noAns = false;
                break ;
            }
        }
        if (noAns) 
            return "-1";
        return dfs (n, a);
    }
    string dfs (int rest,vector<int>& a) {
        string ret;
        for (int i = 0;i < 9;++ i) {
            if (rest >= a [i]) {    //买得起 
                string tmp = to_string(i + 1) + dfs (rest - a [i],a);
                if (cmp(tmp,ret)) {
                    ret = tmp;
                }
            }
        }
        return ret;
    }
};

因为递归枚举了每一个数位，所以时间复杂度为 ,空间复杂度也为 (max_wei为最大的位数)

方法二(正解)

首先，我们可以观察方法一，即暴力解法的特点。
我们比较两个数的大小时，是先比较它们的位数(位数多的数显然更大一些),再以此从高到低比较数位的大小。所以给我们提供了一个思路，也就是最终答案的位数要尽量的大。

(就算最高位更大，也抵不过位数的作用。)
所以策略一，要尽量先保证位数大。而策略二是，在相同位数下，显然越高位的数字越大越好。
例如


相同位数下，只要高位越大，数字越大。
所以在保证了位数足够大后，我们考虑从高到底依次替换当前数字为更大的数字。(注意，是更大的数字，一定不能换成更小的数字)
这样的贪心策略就一定可以保证是最优的答案。
例如1-9价格依次为 ,我们有15元。先按照策略一，计算出最大的位数(max_wei)为 ,所以最大为2位，此时数字位11，然后我们以次从最高位开始，如果退掉那个1，我们就总共有8元，可以买一个9，那我们就换上9，此时就变成了91，是更大的数字。这个时候没有钱换数字了(因为1是最便宜的数字中最大的，我们卖掉1得到的钱不可能买得起更大的数字)。所以91就是答案。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型vector 1-9这九个数字的价格数组
     * @return string字符串
     */
    string buyNumber(int n, vector<int>& a) {
        bool noAns = true;
        for (int i = 0;i < 9;++ i) {
            if (a [i] <= n) {
                noAns = false;
                break ;
            }
        }
        if (noAns) 
            return "-1";
        int cheapest_num = 9;
        for (int i = 8;i >= 0;-- i) {    //这里有个细节，那就是最便宜的数字应该尽可能的大。比如，当1和8的价格一样时，显然优先选择8 
            if (a [i] < a [cheapest_num - 1]) {
                cheapest_num = i + 1;
            }
        }
        int max_wei = n / a [cheapest_num - 1];    //最大的位数
        // 然后看看剩了多少钱
        int money_rest = n - max_wei * a [cheapest_num - 1]; 
        // 从高位替换
        int range = max_wei;
        string ans;
        for (;range >= 1;) {
            // 看看能放哪个
            bool changed = false;
            for (int j = 9;j > cheapest_num;-- j) {    //换成比cheapest_num更小的就没有意思了 
                if (money_rest + a [cheapest_num - 1] >= a [j - 1]) {    //可以换成更高的 
                    money_rest =  money_rest + a [cheapest_num - 1] - a [j - 1];
                    changed = true;
                    ans = ans + to_string(j);
                    -- range;
                    break ;
                }
            }
            if (!changed) break;
        }
        for (;range >= 1;-- range) {    //剩下的都是没变的 
            ans = ans + to_string(cheapest_num);
        }
        return ans;
    }
};

因为我们只是依次尝试替换每一个数位，而替换的选项个数是常数9，所以时间复杂度为 ,空间复杂度也为 (max_wei为最大的位数)