蓝桥杯c/c++程序设计——数位排序
数位排序【第十三届】【省赛】【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 的个位数字加到 sumx=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); // 输入第一个整数 ascanf("%d",&b); // 输入第二个整数 bint n[100001]={0}; // 声明一个数组 n,长度为 100001,并初始化为 0for(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 的个位数字加到 sumx=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); // 输入第一个整数 ascanf("%d",&b); // 输入第二个整数 bint n[100001]={0}; // 声明一个数组 n,长度为 100001,并初始化为 0for(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) { // 如果范围内的元素数量大于 1RandomAccessIterator 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++程序设计——数位排序
数位排序【第十三届】【省赛】【C组】 题目描述 小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。 当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。 例如࿰…...

【通讯录案例-搭建登录界面 Objective-C语言】
一、来看我们这个通讯录案例 1.接下来啊,我们来做这个通讯录案例, 然后呢,做这么一个应用程序啊, 我们第一步呢,先把界面儿搭了, 然后呢,搭之前,简单的来分析一下, 首先呢,这是,中间儿的这一块儿, 1)有个“账户”、“密码”,这一块儿, 这是一个什么控制器,…...
二叉搜索树、AVL、红黑树、B树
文章目录 二叉搜索树2. avl树3. 红黑树 b树和b树比较适合与磁盘打交道的,磁盘操作耗时,这些树 矮,红黑树、avL树高,比较适合与内存打交道。 二叉搜索树 找一个节点的前驱和后继: 前驱:如果节点有左子树&a…...
格密码:傅里叶矩阵
目录 一. 铺垫性介绍 1.1 傅里叶级数 1.2 傅里叶矩阵的来源 二. 格基与傅里叶矩阵 2.1 傅里叶矩阵详细解释 2.2 格基与傅里叶矩阵 写在前面:有关傅里叶变换的解释太多了,这篇博客主要总结傅里叶矩阵在格密码中的运用。对于有一定傅里叶变换基础的同…...

flex--伸缩性
1.flex-basis flex-basis 设置的是主轴方向的基准长度,会让宽度或高度失效。 备注:主轴横向:宽度失效;主轴纵向:高度失效 作用:浏览器根据这个属性设置的值,计算主轴上是否有多余空间&#x…...

linux中主从复制的架构和读写分离的方式
读写分离 互相主从架构注意点 双主双从架构注意点 一主多从架构注意点 读写分离概念部署jdk环境上传文件,解压文件配置环境变量 部署mycat环境mycat配置文件给所有数据库创建访问用户配置 server.xml配置 schema.xml启动mycat查看启动端口日志负载均衡测试 遇到的问…...

Ubuntu 22.04.3 Server 设置静态IP 通过修改yaml配置文件方法
目录 1.查看网卡信息 2.修改yaml配置文件 3.应用新的网络配置 4.重新启动网络服务 文章内容 本文介绍Ubuntu 22.04.3 Server系统通过修改yaml配置文件配置静态 ip 的方法。 1.查看网卡信息 使用ifconfig命令查看网卡信息获取网卡名称 如果出现Command ifconfig not fo…...

EasyCVR无人机推流+人数统计AI算法,助力公共场所人群密度管控
一、背景与需求 在公共场所和大型活动的管理中,人数统计和人群密度控制是非常重要的安全问题。传统的方法可能存在效率低下或准确度不足的情况,无法满足现代社会的需求。TSINGSEE青犀可以利用无人机推流AI人流量统计算法,基于计算机视觉技术…...
Kotlin 接口
Kotlin 的接口可以既包含抽象方法的声明也包含实现;接口无法保存状态;可以有属性但必须声明为抽象或提供访问器实现 1、定义 使用关键字 interface 来定义接口 interface MyInterface {fun bar()fun foo() {// 可选的方法体} } 2、 实现接口 一个类…...

Qt前端技术:5.QSS
这个是表示QFrame中的pushButton中的子类和它子类的子类都将背景变为red 写成大于的时候表示只有直接的子类对象才会变 这个图中的QGroupBox和QPushButton都是QFrame的直接的子类 这个中的QGroupBox是QFrame的直接的子类但是QPushButton 是QGroupBox的子类,QPushB…...

在Centos7中利用Shell脚本:实现MySQL的数据备份
目录 自动化备份MySQL 一.备份数据库脚本 1.创建备份目录 2.创建脚本文件 3.新建配置文件(连接数据库的配置文件) 4.给文件权限(mysql_backup.sh) 编辑 5.执行命令 (mysql_backup.sh) 编辑 二.数据库通过备份恢复 1.创建脚…...

大一C语言查缺补漏 12.24
遗留问题: 6-1 1 在C语言中,如果要保留小数的话,一定要除以2.0,而不是2。 设整型变量m,n,a,b的值均为1,执行表达式(m a>b)||(n a<b)后,表达式的值以及变量m和n的值是&#…...
程序员宝典:常用的免费好物API
六位图片验证码生成:包括纯数字、小写字母、大写字母、大小写混合、数字小写、数字大写、数字大小写等情况。 四位图片验证码生成:四位图片验证码生成,包括纯数字、小写字母、大写字母、大小写混合、数字小写、数字大写、数字大小写等情况。…...

关于“Python”的核心知识点整理大全41
目录 scoreboard.py game_functions.py game_functions.py 14.3.8 显示等级 game_stats.py scoreboard.py scoreboard.py scoreboard.py game_functions.py game_functions.py alien_invasion.py 14.3.9 显示余下的飞船数 ship.py scoreboard.py 我们将最高得分圆整…...

java进阶(二)-java小干货
java一些精干知识点分享 2. java小干货2.1循环遍历2.2可变参数2.3 list和数组转化2.3.1 数组转list2.3.2 list转数组 2.4 值传递和地址传递2.4.1值传递2.4.2 地址传递2.4.3易错点总结 2.5 数据类型2.5.1基础知识2.5.2 基础数据和包装类 2.6 字符串2.6.1 char/String区别2.6.2 .…...

layui(iconPickerFa)图标选择器插件,主要用于后台菜单图标管理
话不多说直接上代码 在页面中引入如下代码 <link rel"stylesheet" href"/template/admin/layui-v2.5.6/css/layui.css"> <script type"text/javascript" src"/template/admin/layui-v2.5.6/layui.js"></script> &…...

RabbitMQ入门指南(九):消费者可靠性
专栏导航 RabbitMQ入门指南 从零开始了解大数据 目录 专栏导航 前言 一、消费者确认机制 二、失败重试机制 三、失败处理策略 四、业务幂等性 1.通过唯一标识符保证操作的幂等性 2.通过业务判断保证操作的幂等性 总结 前言 RabbitMQ是一个高效、可靠的开源消息队列系…...
MySQL的聚合函数、MySQL的联合查询、MySQL的左连接右连接内连接
MySQL的聚合函数 MySQL聚合函数是在数据库中对数据进行聚合操作的函数。它们将多行数据作为输入,并返回单个值作为结果。 常用的MySQL聚合函数包括: COUNT:计算符合条件的行数。SUM:对指定列的数值进行求和操作。AVG࿱…...
RKNN Toolkit Lite2 一键安装和测试,sh脚本
RKNN Toolkit Lite2 安装和测试教程 本教程旨在指导用户如何使用提供的shell脚本来安装和测试RKNN Toolkit Lite2,适用于需要在Linux系统上部署和测试AI模型的开发者。 简介 RKNN Toolkit Lite2是一个高效的AI模型转换和推理工具包,专为Rockchip NPU设…...

探索中国制造API接口:解锁无限商机,引领制造业数字化转型
一、概述 中国制造API接口是一种应用程序接口,专门为中国制造行业提供数据和服务。通过使用API接口,开发者可以轻松地获取中国制造的商品信息、供应商数据、生产能力等,从而为他们的应用程序或网站提供更加丰富的内容和功能。 二、API接口的…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...
字符串哈希+KMP
P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...