正如标题所说，给定一组整数 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 无法识别这给出的任何类型的模式。
到目前为止我得出的结论是，总是会先用完。我没有证据，但确实如此。
任何人都可以提出任何建议吗？多谢。
EDIT:
感谢 btilly 的指点（请参阅下面他的帖子和评论。也标记为解决方案），我想出了并实现了一种有效的方法来查找数字 1...n 的成本。在我实现了二分搜索以查找今天晚些时候可以用给定股票写入的最后一个数字之后，我将进一步详细说明这一点。
编辑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), where n是我们要获取成本的数字，并且d is the d第 ' 位数字来自n我们目前正在合作。我们还定义一个方法D(n, d)这将返回d第 ' 位数字来自n。然后我们将应用以下逻辑：
sum = C(n, d)
if D(n, d) is 1:
for each k < d, k >= 0 :
sum -= ( 9 - D(n, k) ) * 10^(k-1);
else if D(n, d) is 0:
sum -= 10^(d-1)
这样，程序将有效地计算出某个数字的正确成本。之后，我们只需应用二分搜索来查找具有正确成本的数字。
