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

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

例如，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≤106。

输入样例：
13
5
输出样例：
3
样例解释
1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。

第 5 个数为 3。

• 快速排序O(nlogn)O(nlogn)O(nlogn)
• 注意要先预处理数位和，不要在cmp中处理，否则会tle
• w[i]表示i的数位和

#include 
#include 
using namespace std;
const int N = 1e6 + 10;int n, m;
int a[N], w[N];int main() {cin >> n >> m;for (int i = 1; i <= n; ++ i) {a[i] = i;for (int j = i; j; j /= 10) {w[i] += j % 10;}}sort(a + 1, a + n + 1, [&](int u, int v) {if (w[u] != w[v]) return w[u] < w[v];return u < v;});cout << a[m];
}

• 快速选择O(n)O(n)O(n)
• 相比于sort，就是将sort换成了nth_element和在a + 1和a + n + 1之间加了a + m

#include 
#include 
using namespace std;
const int N = 1e6 + 10;int n, m;
int a[N], w[N];int main() {cin >> n >> m;for (int i = 1; i <= n; ++ i) {a[i] = i;for (int j = i; j; j /= 10) {w[i] += j % 10;}}nth_element(a + 1, a + m, a + n + 1, [&](int u, int v) {if (w[u] != w[v]) return w[u] < w[v];return u < v;});cout << a[m];
}

• 手写快速选择算法O(n)O(n)O(n)

#include 
#include 
using namespace std;
const int N = 1e6 + 10;int n, m;
int a[N], w[N];int cmp(int u, int v) {if (w[u] != w[v]) return w[u] < w[v];return u < v;
}
int quick_select(int l, int r, int k) {if (l == r) return a[l];int x = a[l + r >> 1], i = l - 1, j = r + 1;while (i < j) {do i ++ ; while (cmp(a[i], x));do j -- ; while (cmp(x, a[j]));if (i < j) swap(a[i], a[j]);}if (k <= j) return quick_select(l, j, k);return quick_select(j + 1, r, k);
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++ i) {a[i] = i;for (int j = i; j; j /= 10) {w[i] += j % 10;}}cout << quick_select(1, n, m);
}