第十三届蓝桥杯省赛C++C组-4653. 数位排序

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。

当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如，20222022 排在 409409 前面，因为 20222022 的数位之和是 66，小于 409409 的数位之和 1313。

又如，66 排在 20222022 前面，因为它们的数位之和相同，而 66 小于 20222022。

给定正整数 n，mn，m，请问对 11 到 nn 采用这种方法排序时，排在第 mm 个的元素是多少？

输入格式

输入第一行包含一个正整数 nn。

第二行包含一个正整数 mm。

输出格式

输出一行包含一个整数，表示答案。

数据范围

对于 30%30% 的评测用例，1≤m≤n≤3001≤m≤n≤300。 对于 50%50% 的评测用例，1≤m≤n≤10001≤m≤n≤1000。 对于所有评测用例，1≤m≤n≤1061≤m≤n≤106。

输入样例：

13
5

输出样例：

3

样例解释

11 到 1313 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,91,10,2,11,3,12,4,13,5,6,7,8,9。

第 55 个数为 33。

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e6+10; int a[N],s[N]; int sum(int x) { int cnt=0; while(x) { cnt+=x%10; x/=10; } return cnt; } bool cmp(int a,int b) { if(s[a]==s[b])return a<b; else return s[a]<s[b]; } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { a[i]=i; s[i]=sum(i); } sort(a+1,a+n+1,cmp); cout<<a[m]<<endl; return 0; }