数位排序【第十三届】【省赛】【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
	}
}

 

1. 如果两个整数的数位之和不相等，则比较它们的数位之和：数位之和较小的整数更小，返回 true。
2. 如果两个整数的数位之和相等，则比较它们的大小：较小的整数更小，返回 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() 源码可能会更加复杂且具有优化。