蓝桥杯c/c++程序设计——数位排序

2023-12-24 21:11:08

数位排序【第十三届】【省赛】【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函数中,用户输入两个整数ab,然后声明一个长度为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() 源码可能会更加复杂且具有优化。

文章来源:https://blog.csdn.net/weixin_66547608/article/details/135185205
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。