这道题直接暴力做的话,时间复杂度在10的8次方左右,由于一开始的位数比较小,所以暴力是勉强能过的。
但是这道题需要注意排序的次序,因此我们可以考虑用pair,pair的第一个位置写数位和,下一个位置写这个数本身,这样就可以保证第一个位置相同按照第二个位置排序的效果。
/*
7*10^6*6log10=7*6*3*10^6=126*10^6=10^8
*/
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef pair<int ,int> pii;
const int N=1e6+10;
pii b[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int tmp=i;
while(tmp)
{
b[i].first+=tmp%10;
tmp/=10;
}
b[i].second=i;
}
sort(b+1,b+n+1);
// for(int i=1;i<=n;i++)
// {
// cout<<"("<<b[i].first<<" "<<b[i].second<<")";
// }
// cout<<endl;
cout<<b[m].second<<endl;
return 0;
}