【蓝桥杯】 C++ 数位排序

题目描述

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。

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

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

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

输入描述

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

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

输出描述

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

实现代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+3;
int num[maxn]={0}; // 从 1 到 n
int sum[maxn]={0}; // 每个数字的各位和

bool cmp(int x,int y)
{
    return (sum[x]<sum[y]) || (sum[x]==sum[y] && x<y);
}

int main()
{
    int n,m;
    cin>>n;
    cin>>m;

    for(int i=1;i<=n;i++)
    {
        int temp=i; // 这个是循环变量用来计算 sum
        num[i]=i;
        while (temp!=0)
        {
            sum[i]=temp%10+sum[i];
            temp=temp/10;
        }
    }
    // 注意因为数组是从 1 开始的所以排序的时候也要从数组地址+1 开始排序
    sort(num+1,num+1+n,cmp);
    cout<<num[m]<<endl;
}

解题思路

题目要求对数位和排序则需要一个数组对其进行记录。还需要一个数组对从 1 到 n 进行记录。

首先读入数据 n 通过模运算和除法运算计算数位和并存入数组 sum 中。然后通过 cmp() 函数对数组 num 进行排序。

注意点

这道题的 cmp() 函数是最重要的地方通过它进行排序。
其次是 sort() 函数在排序的时候需要注意因为前面是从 1 开始的所以排序的首位也要加 1。

    // 注意因为数组是从 1 开始的所以排序的时候也要从数组地址+1 开始排序
    sort(num+1,num+1+n,cmp);

知识点

• sort() 函数详解见C++ sort()排序详解。