解题思路:用记忆化搜索(或是递推)求出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;
}
0.0分
1 人评分
不容易系列2 (C语言代码)浏览:654 |
简单编码 (C++代码)(这里推荐用switch)浏览:964 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:590 |
printf基础练习2 (有点不明白)浏览:845 |
【蟠桃记】 (C语言代码)浏览:669 |
C语言程序设计教程(第三版)课后习题6.8 (C++代码)浏览:592 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:473 |
核桃的数量 (C语言代码)浏览:672 |
Tom数 (C语言代码)浏览:529 |
C二级辅导-等差数列 (C语言代码)浏览:724 |