AcWing 4653. 数位排序
原题链接
简单
作者:
YOLO_0
,
2023-01-03 21:46:48
,
所有人可见
,
阅读 107
本质上为归并排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int a[N], b[N], tem[N];
int n, m;
int num(int x) // 求数位和
{
int y = 0;
while (x)
{
y += x % 10;
x /= 10;
}
return y;
}
void merger_sort(int l, int r)
{
if (l >= r) return ;
int mid = (l + r) >> 1;
merger_sort(l, mid), merger_sort(mid + 1, r);
int k = 1, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (b[a[i]] < b[a[j]]) tem[k ++] = a[i ++];
else if (b[a[i]] == b[a[j]]) // 数位和相等时,值小的在前面
{
if (a[i] < a[j]) tem[k ++] = a[i ++];
else tem[k ++] = a[j ++];
}
else tem[k ++] = a[j ++];
}
while (i <= mid) tem[k ++] = a[i ++];
while (j <= r) tem[k ++] = a[j ++];
for (int i = l, j = 1; i <= r; i ++, j ++) a[i] = tem[j];
}
int main()
{
int x;
cin >> n >> m;
for (int i = 1; i <= n; i ++) a[i] = i, b[a[i]] = num(a[i]); // b数组存储数位和
merger_sort(1, n);
cout << a[m] << endl;
return 0;
}