数位排序

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

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

例如，\(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\)。

Code

#include<iostream>
#include<algorithm>
#include<vector> 
#define X first
#define Y second

using namespace std;

typedef pair<int,int> PII;
int n,m; 
const int N = 1e6 + 10;
vector<PII> q;

int get(int x){
	int ret = 0;
	while(x){
		ret += x % 10;
		x /= 10;
	}
	return ret;
}

bool cmp(PII a,PII b){
	if(a.Y != b.Y)return a.Y < b.Y;
	else return a.X < b.X;
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)q.push_back({i,get(i)});
	sort(q.begin(),q.end(),cmp);
	cout << q[m - 1].first;
}

注意

1. vector从0开始而不是1
2. nlogn时间复杂度 -> 先对每个数进行预处理，保存数位和再进行排序，而不是排序过程中进行处理