题目描述

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

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

例如，$2022$ 排在 $409$ 前面，因为 $2022$ 的数位之和是 $6$，小于 $409$ 的数位之和 $13$。

又如，$6$ 排在 $2022$ 前面，因为它们的数位之和相同，而 $6$ 小于 $2022$。

给定正整数 $n, m$，请问对 $1$ 到 $n$ 采用这种方法排序时，排在第 $m$ 个的元素是多少？

输入格式

输入第一行包含一个正整数 $n$。

第二行包含一个正整数 $m$。

输出格式

输出一行包含一个整数，表示答案。

数据范围

对于 $30 \%$ 的评测用例，$1 \le m \le n \le 300$。
对于 $50 \%$ 的评测用例，$1 \le m \le n \le 1000$。
对于所有评测用例，$1 \le m \le n \le 10 ^ 6$。

输入样例：

13
5

输出样例：

3

样例解释

$1$ 到 $13$ 的排序为：$1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9$。

第 $5$ 个数为 $3$。

解题思路

我们可以先把 $1 \sim n$ 这 $n$ 个数存进数组 $a$ 里，记 $f _ i$ 为 $i$ 的数位个数之和，按照数位之和为第一关键字，数的真实大小为第二关键字对 $a$ 进行排序，输出 $a _ m$ 即可。

时间复杂度：预处理 $f$ 数组：$n \log n$；排序：$n \log n$；总时间复杂度：$n \log n$。

AC Code

#include <iostream>
#include <algorithm>
#define N 1000005
using namespace std;

int n, m, a[N], f[N];

bool cmp (int x, int y) // 比较函数
{
    if (f[x] == f[y])
    {
        return x < y;
    }
    return f[x] < f[y];
}

int main ()
{
    cin >> n >> m;
    for (int i = 1, b, s; i <= n; i ++)
    {
        a[i] = b = i, s = 0;
        while (b)
        {
            s += b % 10, b /= 10;
        }
        f[i] = s; // i 各数位之和
    }
    sort (a + 1, a + n + 1, cmp), cout << a[m]; // 排序并输出答案
    return 0;
}

感谢观看！

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {DarkOrchid} {【寒假每日一题】题解}}$$