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

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

思路

  1. 我们知道这是一个小根堆,堆顶元素是最小的,我们可以将堆顶元素取出,将其放入res数组中,然后将堆顶元素删除,注意,在这一步当中是不用关注初始化顺串的元素的。
  2. 然后将初始的顺串中的下一个元素放入堆中,然后调整堆,使其满足堆的性质。
    1. 如果初始的顺串被选中的元素比res数组中的最后一个元素大,那么就将这个元素放入堆中,然后调整堆;否则将这个元素先放入堆,然后与堆的最后一个元素交换,堆的大小减一,最后调整堆。
  3. 然后将堆顶元素取出,放入res数组中,然后将堆顶元素删除。
  4. 重复上述步骤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 描述 给定初始整数顺串&#xff0c;以及大小固定并且初始元素已知的二叉最小堆&#xff08;为完全二叉树或类似完全二叉树&#xff0c;且父元素键值总小于等于任何一个子结点的键值&#xff09;&#xff0c;要求利用堆实现置换选择排序&a…...

如何提取b站的视频字幕,下载视频

打开视频地址 按F12打开—开发者工具 在开发者工具打开Network 过滤器关键字&#xff1a; 自动生成字幕&#xff1a;ai_subtitle 自制&#xff1a;json 打开/关闭字幕 刷新页面 找到字幕 点选字幕的respond 将方框中的内容复制&#xff1b; 复制到&#xff1a;https://www.drea…...

Vue中使用ECharts实现热力图的详细教程

在数据可视化领域&#xff0c;热力图是一种非常直观的表现形式&#xff0c;它通过颜色深浅来展示数据分布情况。在Vue项目中&#xff0c;我们可以使用ECharts这一强大的图表库来实现热力图。下面我将详细介绍如何在Vue中使用ECharts实现热力图。效果如下图&#xff1a; 一、准备…...

Arduino UNO R3自学笔记13 之 Arduino使用LM35如何测量温度?

注意&#xff1a;学习和写作过程中&#xff0c;部分资料搜集于互联网&#xff0c;如有侵权请联系删除。 前言&#xff1a;学习使用传感器测温。 1.LM35介绍 一般来讲当知道需求&#xff0c;就可以 通过既定要求的条件来筛选需要的器件&#xff0c;多方面的因素最终选定了器件…...

蓝桥杯【物联网】零基础到国奖之路:十六. 扩展模块之矩阵按键

蓝桥杯【物联网】零基础到国奖之路:十六. 扩展模块之矩阵按键 第一节 硬件解读第二节 CubeMX配置第三节 MDK代码 第一节 硬件解读 扩展模块和ADC模块是一摸一样的&#xff0c;插在主板上。 引脚对应关系&#xff1a; PB6-ROW1 PB7-ROW2 PB1-COLUMN1 PB0-COLUMN2 PA8-COLUMN3 …...

Apollo9.0 Planning2.0决策规划算法代码详细解析 (4): PlanningComponent::Proc()

&#x1f31f; 面向自动驾驶规划算法工程师的专属指南 &#x1f31f; 欢迎来到《Apollo9.0 Planning2.0决策规划算法代码详细解析》专栏&#xff01;本专栏专为自动驾驶规划算法工程师量身打造&#xff0c;旨在通过深入剖析Apollo9.0开源自动驾驶软件栈中的Planning2.0模块&am…...

AAA Redis的过期删除策略+缓存雪崩+缓存一致性问题

目录 一、三种删除策略比较 二、缓存雪崩缓存击穿缓存穿透 三、缓存一致性 Redis学习笔记 一、三种删除策略比较 内存占用CPU占用特征定时删除节约内存&#xff0c;无占用不分时段占用CPU资源&#xff0c;频度高时间换空间惰性删除内存占用严重延时执行&#xff0c;CPU利用…...

成都跃享未来教育咨询有限公司抖音小店:引领教育咨询新风尚

在数字化浪潮席卷全球的今天&#xff0c;教育咨询行业正经历着前所未有的变革。成都跃享未来教育咨询有限公司&#xff0c;作为教育行业的一颗璀璨新星&#xff0c;凭借其前瞻性的教育理念与创新的运营模式&#xff0c;在抖音平台上开设了小店&#xff0c;不仅为广大学子及家长…...

【堆排】为何使用向下调整法建堆比向上调整法建堆更好呢?

文章目录 前言一、堆排代码一、计算使用向上调整法建堆的时间复杂度二、计算使用向下调整法插入的时间复杂度总结 前言 在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好&#xff0c;是因为使用向上调整法建堆的时间复杂…...

在Stable Diffusion WebUI中安装SadTalker插件时几种错误提示的处理方法

SD中的插件一般安装比较简单&#xff0c;但也有一些插件安装会比较难。比如我在安装SadTalker时&#xff0c;就遇到很多问题&#xff0c;一度放弃了&#xff0c;后来查了一些网上攻略&#xff0c;自己也反复查看日志&#xff0c;终于解决&#xff0c;不吐不快。 一、在Stable …...

使用ffmpeg合并视频和音频

使用ffmpeg合并视频和音频 - 哔哩哔哩 简介 FFmpeg是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的完整解决方案。它包含了非常先进的音频/视频编解码库libavcodec&#xff0…...

周末总结(2024/10/05)

工作 人际关系核心实践&#xff1a; 要学会随时回应别人的善意&#xff0c;执行时间控制在5分钟以内 坚持每天早会打招呼 遇到接不住的话题时拉低自己&#xff0c;抬高别人(无阴阳气息) 朋友圈点赞控制在5min以内&#xff0c;职场社交不要放在5min以外 职场的人际关系在面对利…...

在Ubuntu中自动挂载SMB/CIFS共享

文章目录 0. 引言1. 使用credentials文件存储认证信息2. 挂载点的准备3. 必要软件的安装4. 调整挂载参数5. 测试挂载6. 日志调试 0. 引言 本文是自己挂载共享磁盘的实践记录&#xff0c;将详细介绍如何在Linux系统中配置自动挂载SMB/CIFS共享&#xff0c;并提供一些常见问题的…...

pWnOS2.0 靶机渗透( cms 渗透,php+mysql 网站渗透,密码碰撞)

pWnOS2.0 靶机渗透( ) 靶机介绍 vulnhub 靶机 本地搭建 由于靶机特性&#xff0c;靶机网卡位nat模式扫不到&#xff0c;原来需要改 nat 的地址 参考方法 https://blog.csdn.net/Bossfrank/article/details/131415257 作者主页 https://blog.csdn.net/Bossfrank?typeblog P…...

【AI】AIOT简介

随着技术的快速发展&#xff0c;人工智能AI和物联网IoT已经成为当今最热门的技术领域。AIOT是人工智能和物联网的结合&#xff0c;使物联网设备更加智能化&#xff0c;能够进行自主决策和学习的技术。 通过物联网产生、收集来自不同维度的、海量的数据存储于云端、边缘端&#…...

picgo + typora + gitee图床

Picgo打造个人图床&#xff0c;稳定又安全 解决Typora笔记上传到CSDN图片无法显示的问题 typora中...

【路径规划】多机器人路径规划

摘要 多机器人路径规划在现代自动化、仓储管理及智能交通系统中有着广泛的应用。本文提出了一种基于A*算法的多机器人路径规划方法&#xff0c;旨在解决多机器人在同一环境中的路径冲突问题。通过采用启发式搜索和路径优化策略&#xff0c;机器人能够在保持避障的前提下实现最…...

深度学习Day-35:One-hot独热编码

&#x1f368; 本文为&#xff1a;[&#x1f517;365天深度学习训练营] 中的学习记录博客 &#x1f356; 原作者&#xff1a;[K同学啊 | 接辅导、项目定制] 一、 独热编码原理 独热编码&#xff08;One-Hot Encoding&#xff09;是一种将分类数据转换为二进制向量的方法&#…...

Streamlit 实现登录注册验证

在开发基于 Streamlit 的应用时&#xff0c;用户认证功能是一个常见需求。本文将介绍如何通过两种方式来实现登录注册功能&#xff1a;手动实现 和 使用 Streamlit-Authenticator 库。手动实现虽然灵活&#xff0c;但需要自行处理密码加密、验证等细节&#xff1b;而 Streamlit…...

ASP.NET Zero 多租户介绍

ASP.NET Zero 是一个基于 ASP.NET Core 的应用程序框架&#xff0c;它提供了多租户支持&#xff0c;以下是关于 ASP.NET Zero 多租户的介绍&#xff1a; 一、多租户概念 多租户是一种软件架构模式&#xff0c;允许多个客户&#xff08;租户&#xff09;共享同一套软件应用程序…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...