当前位置: 首页 > news >正文

蓝桥杯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函数中,用户输入两个整数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 的个位数字加到 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}
}

 

  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); // 输入第一个整数 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组】 题目描述 小蓝对一个数的数位之和很感兴趣&#xff0c;今天他要按照数位之和给数排序。 当两个数各个数位之和不同时&#xff0c;将数位和较小的排在前面&#xff0c;当数位之和相等时&#xff0c;将数值小的排在前面。 例如&#xff0…...

【通讯录案例-搭建登录界面 Objective-C语言】

一、来看我们这个通讯录案例 1.接下来啊,我们来做这个通讯录案例, 然后呢,做这么一个应用程序啊, 我们第一步呢,先把界面儿搭了, 然后呢,搭之前,简单的来分析一下, 首先呢,这是,中间儿的这一块儿, 1)有个“账户”、“密码”,这一块儿, 这是一个什么控制器,…...

二叉搜索树、AVL、红黑树、B树

文章目录 二叉搜索树2. avl树3. 红黑树 b树和b树比较适合与磁盘打交道的&#xff0c;磁盘操作耗时&#xff0c;这些树 矮&#xff0c;红黑树、avL树高&#xff0c;比较适合与内存打交道。 二叉搜索树 找一个节点的前驱和后继&#xff1a; 前驱&#xff1a;如果节点有左子树&a…...

格密码:傅里叶矩阵

目录 一. 铺垫性介绍 1.1 傅里叶级数 1.2 傅里叶矩阵的来源 二. 格基与傅里叶矩阵 2.1 傅里叶矩阵详细解释 2.2 格基与傅里叶矩阵 写在前面&#xff1a;有关傅里叶变换的解释太多了&#xff0c;这篇博客主要总结傅里叶矩阵在格密码中的运用。对于有一定傅里叶变换基础的同…...

flex--伸缩性

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

linux中主从复制的架构和读写分离的方式

读写分离 互相主从架构注意点 双主双从架构注意点 一主多从架构注意点 读写分离概念部署jdk环境上传文件&#xff0c;解压文件配置环境变量 部署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算法,助力公共场所人群密度管控

一、背景与需求 在公共场所和大型活动的管理中&#xff0c;人数统计和人群密度控制是非常重要的安全问题。传统的方法可能存在效率低下或准确度不足的情况&#xff0c;无法满足现代社会的需求。TSINGSEE青犀可以利用无人机推流AI人流量统计算法&#xff0c;基于计算机视觉技术…...

Kotlin 接口

Kotlin 的接口可以既包含抽象方法的声明也包含实现&#xff1b;接口无法保存状态&#xff1b;可以有属性但必须声明为抽象或提供访问器实现 1、定义 使用关键字 interface 来定义接口 interface MyInterface {fun bar()fun foo() {// 可选的方法体} } 2、 实现接口 一个类…...

Qt前端技术:5.QSS

这个是表示QFrame中的pushButton中的子类和它子类的子类都将背景变为red 写成大于的时候表示只有直接的子类对象才会变 这个图中的QGroupBox和QPushButton都是QFrame的直接的子类 这个中的QGroupBox是QFrame的直接的子类但是QPushButton 是QGroupBox的子类&#xff0c;QPushB…...

在Centos7中利用Shell脚本:实现MySQL的数据备份

目录 自动化备份MySQL 一.备份数据库脚本 1.创建备份目录 2.创建脚本文件 3.新建配置文件&#xff08;连接数据库的配置文件&#xff09; 4.给文件权限(mysql_backup.sh) ​编辑 5.执行命令 (mysql_backup.sh) ​编辑 二.数据库通过备份恢复 1.创建脚…...

大一C语言查缺补漏 12.24

遗留问题&#xff1a; 6-1 1 在C语言中&#xff0c;如果要保留小数的话&#xff0c;一定要除以2.0&#xff0c;而不是2。 设整型变量m,n,a,b的值均为1&#xff0c;执行表达式&#xff08;m a>b&#xff09;||(n a<b)后&#xff0c;表达式的值以及变量m和n的值是&#…...

程序员宝典:常用的免费好物API

六位图片验证码生成&#xff1a;包括纯数字、小写字母、大写字母、大小写混合、数字小写、数字大写、数字大小写等情况。 四位图片验证码生成&#xff1a;四位图片验证码生成&#xff0c;包括纯数字、小写字母、大写字母、大小写混合、数字小写、数字大写、数字大小写等情况。…...

关于“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聚合函数是在数据库中对数据进行聚合操作的函数。它们将多行数据作为输入&#xff0c;并返回单个值作为结果。 常用的MySQL聚合函数包括&#xff1a; COUNT&#xff1a;计算符合条件的行数。SUM&#xff1a;对指定列的数值进行求和操作。AVG&#xff1…...

RKNN Toolkit Lite2 一键安装和测试,sh脚本

RKNN Toolkit Lite2 安装和测试教程 本教程旨在指导用户如何使用提供的shell脚本来安装和测试RKNN Toolkit Lite2&#xff0c;适用于需要在Linux系统上部署和测试AI模型的开发者。 简介 RKNN Toolkit Lite2是一个高效的AI模型转换和推理工具包&#xff0c;专为Rockchip NPU设…...

探索中国制造API接口:解锁无限商机,引领制造业数字化转型

一、概述 中国制造API接口是一种应用程序接口&#xff0c;专门为中国制造行业提供数据和服务。通过使用API接口&#xff0c;开发者可以轻松地获取中国制造的商品信息、供应商数据、生产能力等&#xff0c;从而为他们的应用程序或网站提供更加丰富的内容和功能。 二、API接口的…...

UE5 学习系列(二)用户操作界面及介绍

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

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

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

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

字符串哈希+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)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...