蓝桥杯2022第十三届省赛真题——数位排序

解题思路:用记忆化搜索（或是递推）求出1-n的每个数的数位和，时间复杂度为O(n),然后用sort排序，时间复杂度为O(nlogn),最后输出排序后的第m个位置的数

注意事项:  不会超时

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;

int dp[N];

int dfs(long long int n)

{

    if(n==0)

    {

        dp[0]=0;

        return 0;

    }

    if(dp[n]!=-1) return dp[n];

    int g=n%10;

    dp[n]=dfs(n/10)+g;

    return dp[n];

}

struct rec{

  long long int shu;

  int h;

}b[N];

long long int n,m;

bool cmp(rec a,rec b)

{

    if(a.h!=b.h) return a.h<b.h;

    else return a.shu<b.shu;

}

int main()

{

    memset(dp,-1,sizeof(dp));

    cin>>n>>m;

    for(long long int i=1;i<=n;i++)    {b[i].h=dfs(i);b[i].shu=i;}

    sort(b+1,b+n+1,cmp);

    cout<<b[m].shu<<endl;

    return 0;

}