求其位数和为10的第k个最小数

Question

寻找替代算法

#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;

}

#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;

}

因此，需要更有效的替代算法。提前致谢

Answer 1

这是必需的数字动态程序的完整性。这一个将让您找到20万（更不用说20,000）几乎立即与二分搜索。

JavaScript代码：

function g(digits, i, sum, bound, memo){
  const key = String([i, sum, bound]);

  if (memo.hasOwnProperty(key))
    return memo[key];
    
  if (sum == 0)
    return memo[key] = 1;
    
  if (i == 0)
    return sum <= (bound ? digits[0] : 9);

  let result = 0;
  
  const k = bound ? digits[i] : 9;

  for (let d=0; d<=k && d<=sum; d++){
    const _bound = digits[i] == d ? bound : 0;
    result += g(digits, i-1, sum-d, _bound, memo);
  }
  
  return result;
}


function f(n, sum){
  const digits = [];
  
  while(n){
    digits.push(n % 10);
    n = Math.floor(n/10);
  }
  
  return g(digits, digits.length-1, sum, 1, {});
}

console.log(f(320002210, 10));

console.log(f(320002209, 10));