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

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

文章目录

• • 题目描述
  • • • • 输入描述
        • 输出描述
  • 实现代码
  • 解题思路
  • 注意点
  • 知识点

题目描述

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

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

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

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

输入描述

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

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

输出描述

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

实现代码

代码1：

#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; // 这个是循环变量，用来计算 sumnum[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;
}

代码2：

#include<bits/stdc++.h>
using namespace std;int num[1000001];
int sum[1000001]={0};bool cmp(int x,int y)
{if((sum[x]<sum[y])||(sum[x]==sum[y]&&x<y)){return true;}else {return false;}
}int main()
{int n,m;cin>>n;cin>>m;for(int i=1;i<=n;i++){// 把数字存到各自数组内num[i]=i;}int shang,yu=0;for(int i=1;i<=n;i++){shang=i;while(shang>0){yu=shang%10;sum[i]=sum[i]+yu;shang=shang/10;}}sort(num+1,num+n+1,cmp); // 根据sum对num排序cout<<num[m];    
}

解题思路

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

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

注意点

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

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

• 注意最后是根据sum的结果对num进行排序，取num里面的数，这一步很重要…………

知识点

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