给定一个整数0-9的存量，在我用完一些整数之前，我可以写的最后一个数字是多少？
正如标题所说，给定0-9的整数，在我用完一些整数之前，我能写的最后一个数字是多少？
因此，如果我给了一个库存，比如从0到9的每个数字为10，那么在我用完一些数字之前，我可以写的最后一个数字是多少。 例如，股票为2我可以写数字1 … 10：
1 2 3 4 5 6 7 8 9 10
在这一点上我的股票是0，我不能写11.还要注意，如果给我一个3的股票，我仍然只能写1 … 10，因为11将花费我2个，这将将我的股票留给-1。
到目前为止我得到了什么：
public class Numbers { public static int numbers(int stock) { int[] t = new int[10]; for (int k = 1; ; k++) { int x = k; while (x > 0) { if (t[x % 10] == stock) return k-1; t[x % 10]++; x /= 10; } } } public static void main(String[] args) { System.out.println(numbers(4)); } } 有了这个，我可以得到相当大的股票大小的正确答案。 当库存大小为10 ^ 6时，代码在~2秒内完成，并且库存为10 ^ 7个数字需要整整27秒。 这还不够好，因为我正在寻找一种能够处理大到10 ^ 16的库存大小的解决方案，所以我可能需要一个O（log（n））解决方案。
这是一个像作业一样的作业，所以我没有来这里没有与这个泡菜摔跤很长一段时间。 我没有通过谷歌搜索得到任何类似的东西，并且wolfram alpha不承认这给出了任何类型的模式。
到目前为止我得出的结论是，总会先消失。 我没有证据，但事实确实如此。
任何人都可以提出任何建议吗？ 非常感谢。
编辑：
我已经提出并实现了一种有效的方法来查找数字1 … n的成本，这要归功于btilly的指针（请参阅下面的post和评论。也标记为解决方案）。 在我实施二进制搜索以找到你今天晚些时候可以用给定股票编写的最后一个数字后，我将进一步详细说明。
编辑2：解决方案
我完全忘记了这篇文章，所以我很抱歉没有在我的解决方案中进行编辑。 不过，我不会复制实际的实现。
我查找数字成本的代码执行以下操作：
首先，让我们选择一个数字，例如9999.现在我们将通过总计每个数十位的成本得到成本，如下所示：
9 9 9 9 ^ ^ ^ ^ ^ ^ ^ roof(9999 / 10^1) * 10^0 = 1000 ^ ^ roof(9999 / 10^2) * 10^1 = 1000 ^ roof(9999 / 10^3) * 10^2 = 1000 roof(9999 / 10^4) * 10^3 = 1000
因此9999的成本是4000。
256相同：
2 5 6 ^ ^ ^ ^ ^ roof(256 / 10^1) * 10^0 = 26 ^ roof(256 / 10^2) * 10^1 = 30 roof(256 / 10^3) * 10^2 = 100
因此256的成本是156。
实现这个想法将使程序仅使用没有数字1或0的数字，这就是需要进一步逻辑的原因。 让我们调用上面解释的方法C（n，d） ，其中n是我们得到成本的数字， d是我们当前使用的n的第n位数。 让我们定义一个方法D（n，d） ，它将从n返回第d ‘个数字。 然后我们将应用以下逻辑：
sum = C(n, d) if D(n, d) is 1: for each k = 0 : sum -= ( 9 - D(n, k) ) * 10^(k-1); else if D(n, d) is 0: sum -= 10^(d-1)
有了这个，程序将有效地计算数字的正确成本。 在此之后，我们只需应用二进制搜索来找到具有正确成本的数字。
步骤1.编写一个有效的函数来计算需要使用多少股票来写入最多为N所有数字。 （提示：使用公式计算用于写出最后一位数字的所有内容，然后使用递归计算在其他数字中使用的所有内容。）
步骤2.进行二分查找以查找您可以使用库存量编写的最后一个数字。
我们可以直接计算答案。 递归公式可以确定从1到10的幂减去1的数量需要多少库存：
f(n, power, target){ if (power == target) return 10 * n + power; else return f(10 * n + power, power * 10, target); } f(0,1,1) = 1 // a stock of 1 is needed for the numbers from 1 to 9 f(0,1,10) = 20 // a stock of 20 is needed for the numbers from 1 to 99 f(0,1,100) = 300 // a stock of 300 is needed for the numbers from 1 to 999 f(0,1,1000) = 4000 // a stock of 4000 is needed for the numbers from 1 to 9999
当它变得复杂时，考虑到我们的计算在任何上述系数的第一个倍数之后所需的额外1 ; 例如，在10（11-19）的第二个倍数上，我们需要为每个数字增加1 。
JavaScript代码：
function f(stock){ var cs = [0]; var p = 1; function makeCoefficients(n,i){ n = 10*n + p; if (n > stock){ return; } else { cs.push(n); p *= 10; makeCoefficients(n,i*10); } } makeCoefficients(0,1); var result = -1; var numSndMul = 0; var c; while (stock > 0){ if (cs.length == 0){ return result; } c = cs.pop(); var mul = c + p * numSndMul; if (stock >= mul){ stock -= mul; result += p; numSndMul++; if (stock == 0){ return result; } } var sndMul = c + p * numSndMul; if (stock >= sndMul){ stock -= sndMul; result += p; numSndMul--; if (stock == 0){ return result; } var numMul = Math.floor(stock / mul); stock -= numMul * mul; result += numMul * p; } p = Math.floor(p/10); } return result; }
输出：
console.log(f(600)); 1180 console.log(f(17654321)); 16031415 console.log(f(2147483647)); 1633388154