小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。
当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？
输入格式
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
输出格式
输出一行包含一个整数，表示答案。
数据范围
对于 30% 的评测用例，1≤m≤n≤300。
对于 50% 的评测用例，1≤m≤n≤1000。
对于所有评测用例，1≤m≤n≤10^6。
输入样例：
13
5
输出样例：
3
样例解释
1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。
第 5 个数为 3。
AC代码如下（题目好理解，主要考虑TLE的问题）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m;
int w[N], s[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
w[i] = i;
for (int j = i; j; j /= 10)
s[i] += j % 10;
}
nth_element(w + 1, w + m, w + n + 1, [&](int a, int b) {
if (s[a] != s[b]) return s[a] < s[b];
return a < b;
});
cout << w[m] << endl;
return 0;
}简单的理解 nth_element() 函数的功能，当采用默认的升序排序规则（std::less<T>）时，该函数可以从某个序列中找到第 n 小的元素 K，并将 K 移动到序列中第 n 的位置处。不仅如此，整个序列经过 nth_element() 函数处理后，所有位于 K 之前的元素都比 K 小，所有位于 K 之后的元素都比 K 大。
当然，我们也可以将 nth_element() 函数的排序规则自定义为降序排序，此时该函数会找到第 n 大的元素 K 并将其移动到第 n 的位置处，同时所有位于 K 之前的元素都比 K 大，所有位于 K 之后的元素都比 K 小。
以下面这个序列为例：
3 4 1 2 5
假设按照升序排序，并通过 nth_element() 函数查找此序列中第 3 小的元素，则最终得到的序列可能为：
2 1 3 4 5
nth_element() 本质也是一个函数模板，定义在<algorithm>头文件中。nth_element() 函数有以下 2 种语法格式：
//排序规则采用默认的升序排序
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last);
//排序规则为自定义的 comp 排序规则
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last,
Compare comp);濒临TLE的代码（快速排序 O(nlogn)）nlogn = 2*10^7，再加上数位加和判断操作，数据卡的严格一点非常容易TLE。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n, m;
int w[N], s[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
w[i] = i;
for (int j = i; j; j /= 10)
s[i] += j % 10;
}
sort(w + 1, w + n + 1, [&](int a, int b) {
if (s[a] != s[b]) return s[a] < s[b];
return a < b;
});
printf("%d\n", w[m]);
return 0;
}
