思路
样例:1 到 13 的排序为:1,10,2,11,3,12,4,13,5,6,7,8,9。
如果数位和相同,则将较小的排到前面。
两个数组 a[], b[]
,a
用来存放原数据,b
用来存放数位和。
自己写个 cmp
函数,用 sort
对 a
进行排序;
cmp
函数逻辑:
- 数位和相同,较小的排到前面
- 数位和不同,数位和较小的排前面
最后输出正确位置,ac。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N], b[N];
int n, m;
bool cmp(int x, int y)
{
// 等于将数据小的排前面
// 不等将数位和小的排前面
if (b[x] == b[y]) {
return x < y;
} else {
return b[x] < b[y];
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
a[i] = i;
int tmp = i;
// 求数位和
while (tmp) {
b[i] += tmp % 10;
tmp /= 10;
}
}
// 对 a 数组,根据 cmp 函数进行排序
sort(a + 1, a + n + 1, cmp);
cout << a[m] << endl;
return 0;
}