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

Question

寻找替代算法

以下是我制作的代码，但在编码网站上被在线法官标记为不正确。

声明 int 数据类型 k 的变量后，l 收到一个输入 使用 cin() 从控制台。 由于问题的约束表明可能的数字是 在 1 到 20000 之间，我首先使用这些条件打开了一个 for 循环。 在 i 的每次迭代中(一个接一个)，都会测试该数字是否其数字相加 到 10，如果是，是否是第 k 个数字之和为 10 的数。

为了求数字之和，我使用了递归函数或使用 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

• 通过记住以前的结果，我可以避免多次执行相同的计算
• 根据各位数字之和的值，调整增量的值

在我的电脑上，计算最大值需要 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;
}