原题链接🔗：4653. 数位排序
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。
当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如， 2022 2022 2022 排在 409 409 409 前面，因为 2022 2022 2022 的数位之和是 6 6 6，小于 409 409 409 的数位之和 13 13 13。
又如， 6 6 6 排在 2022 2022 2022 前面，因为它们的数位之和相同，而 6 6 6 小于 2022 2022 2022。
给定正整数 n n n， m m m，请问对 1 1 1 到 n n n 采用这种方法排序时，排在第 m m m 个的元素是多少？
输入格式
输入第一行包含一个正整数
n
n
n。
第二行包含一个正整数 m m m。
输出格式
输出一行包含一个整数，表示答案。
数据范围
对于 30% 的评测用例，
1
≤
m
≤
n
≤
300
1≤m≤n≤300
1≤m≤n≤300。
对于 50% 的评测用例，
1
≤
m
≤
n
≤
1000
1≤m≤n≤1000
1≤m≤n≤1000。
对于所有评测用例，
1
≤
m
≤
n
≤
1
0
6
1≤m≤n≤10^6
1≤m≤n≤106。
输入样例：
13
5输出样例：
3样例解释
1
1
1 到
13
13
13 的排序为：
1
,
10
,
2
,
11
,
3
,
12
,
4
,
13
,
5
,
6
,
7
,
8
,
9
1,10,2,11,3,12,4,13,5,6,7,8,9
1,10,2,11,3,12,4,13,5,6,7,8,9。
第 5 5 5 个数为 3 3 3。
思路与代码 1. 个人解法使用有序的键值对容器map，其中key是每个数字的数位之和，value是符合相应数位之和的所有数字。例如，当key = 1时，相应的value = [1, 10, 100, ...]，用vector容器来存储。
因为是从小到大遍历的，所以总可以保证两个数字的数位之和相同时，大数在小数后面。
AC代码：
#include#include#include 方法是自定义排序规则。
需要注意的是，我们在比较两个数的大小的时候不能现场去计算它们的数位之和再去比较，否则会TLE。必须先预处理出所有数字的数位之和，然后再进行排序（因为排序的时间复杂度是 O ( n log n ) O(n\log n) O(nlogn)，所以光是排序就要算 2 × 1 0 7 2\times 10^7 2×107 次，而求一个数的数位之和要算 6 6 6 次，如果现场计算的话，则总共要算 1.2 × 1 0 8 1.2\times 10^8 1.2×108 次，有可能会TLE）。
#include#include
using namespace std;
const int N = 1e6 + 10;
struct Node {int val, sum;
} a[N];
bool cmp(const Node &x, const Node &y) {return x.sum< y.sum || x.sum == y.sum && x.val< y.val;
}
int main() {int n, m;
cin >>n >>m;
for (int i = 1; i<= n; i++) {a[i].val = i;
for (int j = i; j; j /= 10) a[i].sum += j % 10;
}
sort(a + 1, a + n + 1, cmp);
cout<< a[m].val<< endl;
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧