OpenJudge | 置换选择排序
总时间限制: 1000ms 内存限制: 65536kB
描述
给定初始整数顺串,以及大小固定并且初始元素已知的二叉最小堆(为完全二叉树或类似完全二叉树,且父元素键值总小于等于任何一个子结点的键值),要求利用堆实现置换选择排序,并输出第一个顺串。例如给定初始顺串29,14,35,13,以及堆(记为16 19 31 25 21 56 40), 置换选择排序得到的第一个顺串为16 19 21 25。

输入
第一行包含两个整数,m为初始顺串的数的个数,n为二叉最小堆的大小
第二行包含m个整数,即初始顺串
第三行包含n个整数,即已经建好的堆的元素(有序,按照从堆顶到堆底,从左到右的顺序)
输出
输出包含一行,即第一个顺串。
样例输入
4 7
29 14 35 13
16 19 31 25 21 56 40
样例输出
16 19 21 25
思路
- 我们知道这是一个小根堆,堆顶元素是最小的,我们可以将堆顶元素取出,将其放入
res数组中,然后将堆顶元素删除,注意,在这一步当中是不用关注初始化顺串的元素的。 - 然后将初始的顺串中的下一个元素放入堆中,然后调整堆,使其满足堆的性质。
- 如果初始的顺串被选中的元素比
res数组中的最后一个元素大,那么就将这个元素放入堆中,然后调整堆;否则将这个元素先放入堆,然后与堆的最后一个元素交换,堆的大小减一,最后调整堆。
- 如果初始的顺串被选中的元素比
- 然后将堆顶元素取出,放入
res数组中,然后将堆顶元素删除。 - 重复上述步骤2、3,直到堆为空或者初始顺串中的元素全部被替换。
看完原理,我们可以将代码分为两个部分,一个是调整堆的代码,一个是置换选择排序的代码。
代码解析
先说调整堆的代码:
void reflushHeap(int n) {int i = 1;while(2*i <= n || 2*i+1 <= n) {if(2*i <= n && 2*i+1 <= n) {if(ar[2*i] < ar[2*i+1]) {if(ar[i] > ar[2*i]) {swap(ar[i], ar[2*i]);i = 2*i;}} else {if(ar[i] > ar[2*i+1]) {swap(ar[i], ar[2*i+1]);i = 2*i+1;}}} else if(2*i <= n && 2*i+1 > n) {if(ar[i] > ar[2*i]) {swap(ar[i], ar[2*i]);i = 2*i;} } else break;}
}
然后是置换选择排序的代码:
这代码在排除输入部分之后是这样的:
while(t--) {if(n <= 0) break;res.push_back(ar[1]);if(res.back() > in[j]) {ar[1] = in[j];swap(ar[1], ar[n]);--n;reflushHeap(n);} else {ar[1] = in[j];reflushHeap(n);}++j;
}
Code
#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;int ar[1024], in[1024];void reflushHeap(int n) {int i = 1;while(2*i <= n || 2*i+1 <= n) {if(2*i <= n && 2*i+1 <= n) {if(ar[2*i] < ar[2*i+1]) {if(ar[i] > ar[2*i]) {swap(ar[i], ar[2*i]);i = 2*i;}} else {if(ar[i] > ar[2*i+1]) {swap(ar[i], ar[2*i+1]);i = 2*i+1;}}} else if(2*i <= n && 2*i+1 > n) {if(ar[i] > ar[2*i]) {swap(ar[i], ar[2*i]);i = 2*i;} } else break;}
}int main() {vector<int> res;ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int m, n, t, j = 1;cin >> m >> n;res.reserve(m);for(int i = 1; i <= m; ++i) {cin >> in[i];}for(int i = 1; i <= n; ++i) {cin >> ar[i];}t = m;while(t--) {if(n <= 0) break;res.push_back(ar[1]);if(res.back() > in[j]) {ar[1] = in[j];swap(ar[1], ar[n]);--n;reflushHeap(n);} else {ar[1] = in[j];reflushHeap(n);}++j;}for(auto i: res) {cout << i << " ";}
}
相关文章:
OpenJudge | 置换选择排序
总时间限制: 1000ms 内存限制: 65536kB 描述 给定初始整数顺串,以及大小固定并且初始元素已知的二叉最小堆(为完全二叉树或类似完全二叉树,且父元素键值总小于等于任何一个子结点的键值),要求利用堆实现置换选择排序&a…...
如何提取b站的视频字幕,下载视频
打开视频地址 按F12打开—开发者工具 在开发者工具打开Network 过滤器关键字: 自动生成字幕:ai_subtitle 自制:json 打开/关闭字幕 刷新页面 找到字幕 点选字幕的respond 将方框中的内容复制; 复制到:https://www.drea…...
Vue中使用ECharts实现热力图的详细教程
在数据可视化领域,热力图是一种非常直观的表现形式,它通过颜色深浅来展示数据分布情况。在Vue项目中,我们可以使用ECharts这一强大的图表库来实现热力图。下面我将详细介绍如何在Vue中使用ECharts实现热力图。效果如下图: 一、准备…...
Arduino UNO R3自学笔记13 之 Arduino使用LM35如何测量温度?
注意:学习和写作过程中,部分资料搜集于互联网,如有侵权请联系删除。 前言:学习使用传感器测温。 1.LM35介绍 一般来讲当知道需求,就可以 通过既定要求的条件来筛选需要的器件,多方面的因素最终选定了器件…...
蓝桥杯【物联网】零基础到国奖之路:十六. 扩展模块之矩阵按键
蓝桥杯【物联网】零基础到国奖之路:十六. 扩展模块之矩阵按键 第一节 硬件解读第二节 CubeMX配置第三节 MDK代码 第一节 硬件解读 扩展模块和ADC模块是一摸一样的,插在主板上。 引脚对应关系: PB6-ROW1 PB7-ROW2 PB1-COLUMN1 PB0-COLUMN2 PA8-COLUMN3 …...
Apollo9.0 Planning2.0决策规划算法代码详细解析 (4): PlanningComponent::Proc()
🌟 面向自动驾驶规划算法工程师的专属指南 🌟 欢迎来到《Apollo9.0 Planning2.0决策规划算法代码详细解析》专栏!本专栏专为自动驾驶规划算法工程师量身打造,旨在通过深入剖析Apollo9.0开源自动驾驶软件栈中的Planning2.0模块&am…...
AAA Redis的过期删除策略+缓存雪崩+缓存一致性问题
目录 一、三种删除策略比较 二、缓存雪崩缓存击穿缓存穿透 三、缓存一致性 Redis学习笔记 一、三种删除策略比较 内存占用CPU占用特征定时删除节约内存,无占用不分时段占用CPU资源,频度高时间换空间惰性删除内存占用严重延时执行,CPU利用…...
成都跃享未来教育咨询有限公司抖音小店:引领教育咨询新风尚
在数字化浪潮席卷全球的今天,教育咨询行业正经历着前所未有的变革。成都跃享未来教育咨询有限公司,作为教育行业的一颗璀璨新星,凭借其前瞻性的教育理念与创新的运营模式,在抖音平台上开设了小店,不仅为广大学子及家长…...
【堆排】为何使用向下调整法建堆比向上调整法建堆更好呢?
文章目录 前言一、堆排代码一、计算使用向上调整法建堆的时间复杂度二、计算使用向下调整法插入的时间复杂度总结 前言 在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好,是因为使用向上调整法建堆的时间复杂…...
在Stable Diffusion WebUI中安装SadTalker插件时几种错误提示的处理方法
SD中的插件一般安装比较简单,但也有一些插件安装会比较难。比如我在安装SadTalker时,就遇到很多问题,一度放弃了,后来查了一些网上攻略,自己也反复查看日志,终于解决,不吐不快。 一、在Stable …...
使用ffmpeg合并视频和音频
使用ffmpeg合并视频和音频 - 哔哩哔哩 简介 FFmpeg是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的完整解决方案。它包含了非常先进的音频/视频编解码库libavcodec࿰…...
周末总结(2024/10/05)
工作 人际关系核心实践: 要学会随时回应别人的善意,执行时间控制在5分钟以内 坚持每天早会打招呼 遇到接不住的话题时拉低自己,抬高别人(无阴阳气息) 朋友圈点赞控制在5min以内,职场社交不要放在5min以外 职场的人际关系在面对利…...
在Ubuntu中自动挂载SMB/CIFS共享
文章目录 0. 引言1. 使用credentials文件存储认证信息2. 挂载点的准备3. 必要软件的安装4. 调整挂载参数5. 测试挂载6. 日志调试 0. 引言 本文是自己挂载共享磁盘的实践记录,将详细介绍如何在Linux系统中配置自动挂载SMB/CIFS共享,并提供一些常见问题的…...
pWnOS2.0 靶机渗透( cms 渗透,php+mysql 网站渗透,密码碰撞)
pWnOS2.0 靶机渗透( ) 靶机介绍 vulnhub 靶机 本地搭建 由于靶机特性,靶机网卡位nat模式扫不到,原来需要改 nat 的地址 参考方法 https://blog.csdn.net/Bossfrank/article/details/131415257 作者主页 https://blog.csdn.net/Bossfrank?typeblog P…...
【AI】AIOT简介
随着技术的快速发展,人工智能AI和物联网IoT已经成为当今最热门的技术领域。AIOT是人工智能和物联网的结合,使物联网设备更加智能化,能够进行自主决策和学习的技术。 通过物联网产生、收集来自不同维度的、海量的数据存储于云端、边缘端&#…...
picgo + typora + gitee图床
Picgo打造个人图床,稳定又安全 解决Typora笔记上传到CSDN图片无法显示的问题 typora中...
【路径规划】多机器人路径规划
摘要 多机器人路径规划在现代自动化、仓储管理及智能交通系统中有着广泛的应用。本文提出了一种基于A*算法的多机器人路径规划方法,旨在解决多机器人在同一环境中的路径冲突问题。通过采用启发式搜索和路径优化策略,机器人能够在保持避障的前提下实现最…...
深度学习Day-35:One-hot独热编码
🍨 本文为:[🔗365天深度学习训练营] 中的学习记录博客 🍖 原作者:[K同学啊 | 接辅导、项目定制] 一、 独热编码原理 独热编码(One-Hot Encoding)是一种将分类数据转换为二进制向量的方法&#…...
Streamlit 实现登录注册验证
在开发基于 Streamlit 的应用时,用户认证功能是一个常见需求。本文将介绍如何通过两种方式来实现登录注册功能:手动实现 和 使用 Streamlit-Authenticator 库。手动实现虽然灵活,但需要自行处理密码加密、验证等细节;而 Streamlit…...
ASP.NET Zero 多租户介绍
ASP.NET Zero 是一个基于 ASP.NET Core 的应用程序框架,它提供了多租户支持,以下是关于 ASP.NET Zero 多租户的介绍: 一、多租户概念 多租户是一种软件架构模式,允许多个客户(租户)共享同一套软件应用程序…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
【WebSocket】SpringBoot项目中使用WebSocket
1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖,添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...
跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践
在电商行业蓬勃发展的当下,多平台运营已成为众多商家的必然选择。然而,不同电商平台在商品数据接口方面存在差异,导致商家在跨平台运营时面临诸多挑战,如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...
EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势
一、WebRTC与智能硬件整合趋势 随着物联网和实时通信需求的爆发式增长,WebRTC作为开源实时通信技术,为浏览器与移动应用提供免插件的音视频通信能力,在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能,对实时…...
shell脚本质数判断
shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数)shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数) 思路: 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...
