数位排序【第十三届】【省赛】【C组】
题目描述
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。
当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6小于 2022。
给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？
输入格式
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
输出格式
输出一行包含一个整数，表示答案。
数据范围
对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300
对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000
对于所有评测用例，1 ≤ m ≤ n ≤ 1e6
输入样例：
13
5
输出样例：
3
样例解释
1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。
第 5 个数为 3。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+1;
int sum(int x)
{
int sum=0;
while(x>0)
{
sum = sum+x%10; // 将 x 的个位数字加到 sum
x=x/10; // 将 x 的数字右移一位
}
return sum; // 返回 x 的各位数字之和
}
int cmp(int a,int b)
{
int sumA=sum(a); // 计算 a 的各位数字之和
int sumB=sum(b); // 计算 b 的各位数字之和
if(sumA!=sumB) // 如果 a 和 b 的各位数字之和不相等
{
return sumA<sumB; // 返回 a 的各位数字之和是否小于 b 的各位数字之和
}
else
{
return a<b; // 返回 a 是否小于 b
}
}
int main()
{
int a,b;
scanf("%d\n",&a); // 输入第一个整数 a
scanf("%d",&b); // 输入第二个整数 b
int n[100001]={0}; // 声明一个数组 n，长度为 100001，并初始化为 0
for(int i=1;i<=a;i++) // 从 1 到 a 进行循环
{
n[i]=i; // 将数组中的第 i 个元素设置为 i
}
sort(n+1,n+a+1,cmp); // 使用 cmp 函数对数组 n 进行排序，从下标 1 开始，到 a 结束
printf("%d",n[b]); // 输出排序后，第 b 个元素
return 0;
}
这段代码是一个对数字进行排序的程序。它首先定义了一个求一个整数各位数字之和的函数sum(int x)，然后定义了一个比较函数cmp(int a, int b)，根据两个数字的各位数字之和进行比较，如果各位数字之和不同，则返回较小的数字，如果各位数字之和相同，则返回较小的数字。在main函数中，用户输入两个整数a和b，然后声明一个长度为100001的整型数组n，将数组初始化为从1到a的整数。然后使用std::sort函数对数组进行排序，排序的依据是调用cmp函数进行比较。最后输出排序后的第b个数字。
分析代码
#include<iostream>
#include<algorithm>
using namespace std;
这是引入所需的库。
const int N=1e6+1;
定义一个常量 N，赋值为 1e6+1，即 1000001。
int sum(int x)
{
int sum=0;
while(x>0)
{
sum = sum+x%10; // 将 x 的个位数字加到 sum
x=x/10; // 将 x 的数字右移一位
}
return sum; // 返回 x 的各位数字之和
}
这是定义了一个函数 sum(int x)，用于计算一个整数各位数字之和。函数内部使用了循环和取模运算来逐个获取 x 的各位数字，然后将其累加到变量 sum 中，最后返回 sum。
int cmp(int a,int b)
{
int sumA=sum(a); // 计算 a 的各位数字之和
int sumB=sum(b); // 计算 b 的各位数字之和
if(sumA!=sumB) // 如果 a 和 b 的各位数字之和不相等
{
return sumA<sumB; // 返回 a 的各位数字之和是否小于 b 的各位数字之和
}
else
{
return a<b; // 返回 a 是否小于 b
}
}
- 如果两个整数的数位之和不相等，则比较它们的数位之和：数位之和较小的整数更小，返回
true。 - 如果两个整数的数位之和相等，则比较它们的大小：较小的整数更小，返回
true；否则返回false。
这个 cmp 函数可以用于对数组进行排序，以实现题目要求。
这是定义了一个比较函数 cmp(int a, int b)，用于在排序时作为比较的依据。函数内部首先调用了 sum 函数计算 a 和 b 的各位数字之和，然后进行比较。如果 a 和 b 的各位数字之和不相等，返回 a 的各位数字之和是否小于 b 的各位数字之和；如果 a 和 b 的各位数字之和相等，返回 a 是否小于 b。
不过请注意，您可能需要事先声明 sum 函数，或者将其放在 cmp 函数的前面，以确保函数之间的调用关系正确。
上面这段代码不太好理解
可以换成下面这个代码：
int cmp(int a,int b)
{
int sumA=sum(a);
int sumB=sum(b);
if(sumA!=sumB)
{
if(sumA<sumB)
{
return true;
}
else
{
return false;
}
}
else
{
if(a<b)
{
return true;
}
else
{
return false;
}
}
}
这样就比较好理解了
int main()
{
int a,b;
scanf("%d\n",&a); // 输入第一个整数 a
scanf("%d",&b); // 输入第二个整数 b
int n[100001]={0}; // 声明一个数组 n，长度为 100001，并初始化为 0
for(int i=1;i<=a;i++) // 从 1 到 a 进行循环
{
n[i]=i; // 将数组中的第 i 个元素设置为 i
}
sort(n+1,n+a+1,cmp); // 使用 cmp 函数对数组 n 进行排序，从下标 1 开始，到 a 结束
printf("%d",n[b]); // 输出排序后，第 b 个元素
return 0;
}
这是程序的主函数 main。首先定义了两个整数变量 a 和 b，然后通过 scanf 函数分别输入这两个整数。接着声明了一个长度为 100001 的整型数组 n，并将其所有元素初始化为 0。
接下来，使用 for 循环将数组 n 的元素从 1 到 a 逐个赋值为对应的值 i。
最后，使用 sort 函数对数组 n 进行排序，排序的依据是调用 cmp 函数进行比较。排序的范围是从下标 1 开始，到下标 a 结束。
最后，使用 printf 函数输出排序后的第 b 个元素。
sort(n+1,n+a+1,cmp);整个程序的作用是，根据用户输入的两个整数 a 和 b，将从 1 到 a 的整数进行排序，排序的依据是各个数字的各位数字之和和大小。然后输出排序后的第 b 个数字。
这行代码使用了 <algorithm> 头文件中的 sort 函数对数组 n 进行排序。下面对该代码进行具体解释：
sort(n+1,n+a+1,cmp);
n+1: 表示指向数组 n 的第二个元素的指针（下标为 1）。n+a+1: 表示指向数组 n 的第 a+1 个元素的指针（下标为 a+1）。这里的a是用户输入的第一个整数。cmp: 表示排序时使用的比较函数，即上文中定义的cmp函数。
该语句的作用是将数组 n 从第二个元素（下标为 1）开始，到第 a+1 个元素（下标为 a+1）结束的元素进行排序。排序的规则是根据 cmp 函数中所定义的比较方式进行排序。排序后，数组 n 中的元素将按照定义好的规则重新排列。
注意，在这里排序的范围是从 1 开始，而不是从 0 开始，因为在这个程序中数组 n 的第一个元素是无效的（初始化为 0），所以从第二个元素开始排序。同时，为了包括第 a 个元素，排序范围到第 a+1 个元素结束。
排序结束后，数组 n 将按照 cmp 函数中定义的规则进行排序的结果。
sort() 是 C++ 标准库中的一个排序算法函数，用于对指定范围内的元素进行排序。
sort() 的函数签名如下：
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
其中，RandomAccessIterator 是一个迭代器类型，用于指定待排序范围的起始位置和结束位置。first 是待排序范围的起始位置的迭代器，last 是待排序范围的结束位置的迭代器，表示右边界（不包含在排序范围内）。
sort() 函数使用的是快速排序算法（平均时间复杂度为 O(n log n)）。下面是 sort() 函数的伪代码实现：
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last)
{
if (first != last && std::distance(first, last) > 1) { // 如果范围内的元素数量大于 1
RandomAccessIterator pivot = std::partition(first + 1, last, std::bind2nd(std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>(), *first));
std::iter_swap(first, pivot - 1); // 将枢纽元放到正确的位置上
sort(first, pivot - 1); // 对左半边范围进行排序
sort(pivot, last); // 对右半边范围进行排序
}
}
sort() 函数使用了 std::partition() 函数来对待排序范围进行划分，将小于枢纽元的元素移到枢纽元的左边，大于枢纽元的元素移到枢纽元的右边。然后递归地对左半边和右半边范围进行排序，直到范围内的元素数量小于等于 1。
需要注意的是，sort() 函数仅保证元素的相对顺序是有序的，而不保证稳定性（相同元素的相对顺序可能会改变）。如果需要保持相同元素的相对顺序不变，可以使用稳定排序算法，比如 std::stable_sort()。
请注意，sort() 的实现可能会因为不同的编译器和标准库而略有不同，伪代码仅用于描述大致实现思路。真正的 sort() 源码可能会更加复杂且具有优化。
![[C/C++]数据结构: 链式二叉树的构建及遍历](https://img-blog.csdnimg.cn/direct/e21f791949d242d3a5551a5aff5e3638.png)
