algorithm - 找出第 K 个数字之和为 10 的最小数

Question

寻找替代算法
以下是我所做的，但在编码网站上被在线裁判标记为不正确的。
在声明了 int 数据类型 k 的变量后，l 收到了一个输入
从控制台使用 cin()。
由于问题的限制是可能的数字是
在 1 到 20000 之间，我首先使用这些条件打开了一个 for 循环。
在 i 的每次迭代中(一个接一个)，测试该数字的数字是否相加
到 10，如果是，则是否是第 k 个数字之和为 10 的数字。
为了找到数字的总和，l 使用了递归函数或使用 while 循环的迭代方法。
因此，这两个代码片段。在这两种方法中，总和是通过首先使用模 % 运算符和除法运算符/查找数字来计算的。计算出总和，然后进一步测试它是否等于 10，如果是，则还通过保持所有先前相似元素的计数来测试它是否是第 K 个元素。满足所有条件后，才是我使用cout()输出的值。

#include <bits/stdc++.h>

using namespace std;

//recursion to get sum of digits.

*int sum(int d)

{

 return d==0?0:d%10+sum(d/10);

}*

int main()

{
  
  //ios_base::sync_with_stdio(false);

  //cin.tie(NULL);

   int t;

   cin>>t;

   while(t-- >0)

   {

    int k;

    cin>>k;

    for(int i=0;i<20000;i++)

    {

     int total=sum(i);

      if(total==10)

     {

      --k;

      if(k==0)

      cout<<i<<"\n";

      }

     }

  }

   return 0;

}

第二个，我使用迭代(while 循环)来推导数字总和

#include <bits/stdc++.h>

using namespace std;

int main()

{
  
  //ios_base::sync_with_stdio(false);

  //cin.tie(NULL);

   int t;

   cin>>t;

   while(t-- >0)

   {

    int k;

    cin>>k;

    for(int i=0;i<20000;i++)

{

     int sum=0,d=i;

     *while(d!=0)

       {

          sum+=d%10;

           d/=10;

       }*


     if(sum==10)

       {

         --k;

          if(k==0)

          cout<<i<<"\n";

        }
    }

 }

return 0;

}

So l need alternative algorithms of better efficiency. Thanks in advance

Answer 1

您的代码的主要问题是您限制了对小于 20000 的值的搜索。
为了提高效率，我加了两个trick

我通过记住以前的结果来避免多次执行相同的计算

根据数字和的值，我调整增量值

在我的 PC 上，计算最大值需要 0.15 秒(对于 k = 20000)。
附加说明
在代码中， i变量对应于候选，即我们测试数字总和是否等于 10 的值。 num对应于找到的解决方案的索引。一个解对应一个数字，其数字之和等于 10。 mem[num] = i意味着 i是 num^th解决方案。 k与 OP 代码中的含义相同:我们想要找到 k^th使数字总和 = 10 的数字。
两行 int kmax = 1; mem[1] = 19;使用 19 的事实是第一个有效的解决方案。这是初始化 mem 的管理所必需的。向量，它记住所有找到的解决方案。
用于加速该过程的技巧如下:

如果当前数的总和i等于10，那么我们知道i之间没有其他解和 i+8 .例如，在 27 之后，下一个解等于 36。所以我们可以做 i += 9而不是简单的 i++ .

如果总和大于 10，那么我们不会通过简单地增加第一位来找到解决方案。例如，如果 i = 85 ，我们可以直接去90 ，即清零最小的数字。这是通过 i += (10 - i%10); 执行的

如果总和小于 10，例如5，那么可以直接加5而不是1。这个是用i += (10 - total);来实现的

在实践中，还有可能走得更远。例如，如果 i = 99000 ，那么我们可以直接添加1000而不是10。我没有走那么远，因为获得的代码似乎已经有点过头了(0.15s而不是1s)。

#include <iostream>
#include <vector>

int sum(int d) {
    int ans = 0;
    while(d) {
        ans += d%10;
        d /= 10;
    }
    return ans;
}

int main() {
    int t;
    std::cin >> t;
    std::vector<int> mem(20001, 0);
    int kmax = 1;
    mem[1] = 19;
    while(t-- >0) {
        int i, k;
        std::cin >> k;
        int num = 1;
        if (k > kmax) {
            i = mem[kmax];
            num = kmax;
            while(true) {
                int total = sum(i);
                if(total == 10) {
                    mem[num] = i;
                    if (num == k) break;
                    num++;
                    i += 9;
                } else {
                    if (total > 10) {
                        i += (10 - i%10);
                    } else {
                        i += (10 - total);
                    }
                }
            }
            kmax = k;
        }
        std::cout << mem[k] <<"\n";
    }
    return 0;
}