题目描述
小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。
当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。
例如,$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$。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1000010;
int n, m;
pii a[N];
int get_sum(int n)
{
int sum = 0;
while(n)
{
sum += (n % 10);
n /= 10;
}
return sum;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
a[i].x = get_sum(i);
a[i].y = i;
}
sort(a + 1, a + 1 + n);
cout << a[m].y << endl;
return 0;
}
手写cmp比较函数复杂度多少呀?大佬
不带这么问的