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

C++:堆排序

堆排序

输入一个长度为n的整数数列,从小到大输出前m小的数

输入格式

第一行包含整数n和m
第二行包含n个整数,表示整数数列

输出格式

共一行,包含m个整数,表示整数数列中前m小的数

数据范围

1 ≤ m ≤ n ≤ 1 0 5 1\le m\le n\le 10^5 1mn105
1 ≤ n u m o f e l e m e n t s i n s e q u e n c e ≤ 1 0 9 1\le num\; of \; elements\; in\; sequence\; \le 10^9 1numofelementsinsequence109

输入样例

5 3
4 5 1 3 2

输出样例

1 2 3

问题分析

堆的基本操作
1.插入一个数 heap[++size] = x; up(size);
2.求集合中的最小值 heap[1];
3.删除最小值 heap[1] = heap[size]; size--; down(1);
4.删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k);
5.修改任意一个元素 heap[k] = x; down(k); up(k);

AC代码

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e5 + 10;int n, m;
int h[N], sz;void down(int u) {int t = u;if(u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if(u != t) {swap(h[u], h[t]);down(t);}
}int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &h[i]);sz = n;for(int i = n / 2; i; i--) down(i);while(m--) {printf("%d ", h[1]);h[1] = h[sz];sz--;down(1);	}return 0;
}

相关文章:

C++:堆排序

堆排序 输入一个长度为n的整数数列&#xff0c;从小到大输出前m小的数 输入格式 第一行包含整数n和m 第二行包含n个整数&#xff0c;表示整数数列 输出格式 共一行&#xff0c;包含m个整数&#xff0c;表示整数数列中前m小的数 数据范围 1 ≤ m ≤ n ≤ 1 0 5 1\le m\le …...

Grafana Prometheus 通过JMX监控kafka

第三方kafka exporter方案 目前网上关于使用Prometheus 监控kafka的大部分资料都是使用一个第三方的 kafka exporter&#xff0c;他的原理大概就是启动一个kafka客户端&#xff0c;获取kafka服务器的信息&#xff0c;然后提供一些metric接口供Prometheus使用&#xff0c;随意它…...

vue项目切换页面白屏不显示解决方案

问题描述 1、页面切换后白屏&#xff0c;同时切换回上一个页面同样白屏 2、刷新后正常显示 3、有警告&#xff1a;Component inside <Transition> renders non-element root node that cannot be animated 解决方法 <Transition>中的组件呈现不能动画化的非元素…...

Goland报错 : Try to open it externally to fix format problem

这句报错的意思也就是 : 尝试在外部打开以解决格式问题 解决方案 : 将图片格式该为.png格式&#xff0c;再粘贴进去就可以了! 改变之后的效果 : 那么&#xff0c;这样就ok了...

Python-OpenCV中的图像处理-几何变换

Python-OpenCV中的图像处理-几何变换 几何变换图像缩放图像平移图像旋转仿射变换透视变换 几何变换 对图像进行各种几个变换&#xff0c;例如移动&#xff0c;旋转&#xff0c;仿射变换等。 图像缩放 cv2.resize() cv2.INTER_AREAv2.INTER_CUBICv2.INTER_LINEAR res cv2.r…...

前端JavaScript入门-day08-正则表达式

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 介绍 语法 元字符 边界符 量词 字符类&#xff1a; 修饰符 介绍 正则表达式&#xff08;Regular …...

ML类CFAR检测器在不同环境中检测性能的分析

摘要&#xff1a;该文是楼主翻阅书籍以及一些论文总结出来的关于ML(均值)类CFAR检测器在不同环境中的性能对比&#xff0c;以及优缺点的总结&#xff0c;可以帮助大家面对不同情形如何选择CFAR问题。由于楼主见识短浅&#xff0c;文中难免出现不足之处&#xff0c;望各位指出。…...

element-ui 路由动态加载功能

第一步 自定义默认的静态路由像登陆和首页这些一般开放的页面&#xff0c;主要代码如下: const router new Router({routes: [{path: "/login/index",component: () > import("../components/page/login/index.vue"),meta: {title: "登录",k…...

(学习笔记-进程管理)进程调度

进程都希望自己能够占用CPU进行工作&#xff0c;那么这涉及到前面说过的进程上下文切换。 一旦操作系统把进程切换到运行状态&#xff0c;也就意味着该进程占用着CPU在执行&#xff0c;但是操作系统把进程切换到其他状态的时候&#xff0c;就不能在CPU中执行了&#xff0c;于是…...

十分钟python入门 正则表达式

正则常见的三种功能&#xff0c;它们分别是&#xff1a;校验数据的有效性、查找符合要求的文本以及对文本进行切割和替换等操作。 1.元字符 所谓元字符就是指那些在正则表达式中具有特殊意义的专用字符 元字符大致分成这几类&#xff1a;表示单个特殊字符的&#xff0c;表示…...

关于数据拷贝赋值方法

系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言一、关于数据拷贝赋值方法1、最基础数据类型的变量才可以直接拷贝赋值2、自己定义的大数据类型或者时类实例化的对象不可以直接拷贝赋值1、方法一:…...

Effective Java笔记(32)谨慎并用泛型和可变参数

故事的小黄花 从出生那年就飘着 童年的荡秋千 随记忆一直晃到现在 可变参数&#xff08; vararg &#xff09; 方法&#xff08;详见第 53 条&#xff09;和泛型都是在 Java 5 中就有了&#xff0c;因此你可能会期待它们可以良好地相互作用&#xff1b;遗憾的是&#xff0c;它们…...

数据结构——双向链表

双向链表实质上是在单向链表的基础上加上了一个指针指向后面地址 单向链表请参考http://t.csdn.cn/3Gxk9 物理结构 首先我们看一下两种链表的物理结构 我们可以看到&#xff1a;双向在单向基础上加入了一个指向上一个地址的指针&#xff0c;如此操作我们便可以向数组一样操作…...

Declare 关键字在 TypeScript 中如何正确使用?

如果您编写 TypeScript 代码的时间足够长,您就已经看到过declare关键字。但它有什么作用,为什么要使用它? declare关键字告诉 TypeScript 编译器存在一个对象并且可以在代码中使用。 本文解释了声明关键字并通过代码示例展示了不同的用例。 定义 在 TypeScript 中,decl…...

ChatGPT将会成为强者的外挂?—— 提高学习能力

目录 前言 一、提高学习力 &#x1f9d1;‍&#x1f4bb; 1. 快速找到需要的知识 2. 组合自己的知识体系 3. 内化知识技能 二、提问能力❗ 三、思维、创新能力 &#x1f31f; 1. 批判性思维 1.1 八大基本结构进行批判性提问 1.2 苏格拉底的提问分类方法 2. 结构化思…...

AUTOSAR规范与ECU软件开发(基础篇)1.3 车用控制器软件标准(从OSEK到AUTOSAR)

目录 AUTOSAR的前世与今生 1.1~1.3篇幅小结 AUTOSAR的前世与今生 为了迎合汽车高精度、 高实时性、 高可靠性控制的需要, 嵌入式实时操作系统(Real Time Operating System, RTOS) 逐渐在ECU中使用。与此同时, 由于不同实时操作系统间应用程序接口(Application Programmi…...

R语言5_安装Giotto

环境Ubuntu22/20, R4.1. 已开启科学上网。 第一步&#xff0c;更新服务器环境&#xff0c;进入终端&#xff0c;键入如下命令&#xff0c; apt-get update apt install libcurl4-openssl-dev libssl-dev libxml2-dev libcairo2-dev libgtk-3-dev libhdf5-dev libmagick9-dev …...

centos按用户保存历史执行命令

centos7 按用户记录历史命令的方法 在/etc/profile文件中添加以下代码。 添加完成后执行source /etc/profile 用户重新登录即可发现history被清空了。这时可以去看/usr/share/.history文件夹&#xff0c;该文件夹保存了所有用户每次登录所执行过的的操作记录。 文件路径为 /usr…...

【力扣】61. 旋转链表 <快慢指针>

【力扣】61. 旋转链表&#xff08;每个节点向右移k个单位&#xff09; 给你一个链表的头节点 head &#xff0c;旋转链表&#xff0c;将链表每个节点向右移动 k 个位置。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], k 2 输出&#xff1a;[4,5,1,2,3] 示例 2&a…...

编写一个指令(v-focus2end)使输入框文本在聚焦时焦点在文本最后一个位置

项目反馈输入框内容比较多时候&#xff0c;让鼠标光标在最后一个位置&#xff0c;心想什么奇葩需求&#xff0c;后面试了一下&#xff0c;是有点影响体验&#xff0c;于是就有了下面的效果&#xff0c;我目前的项目都是若依的架子&#xff0c;用的是vue2版本。vue3的朋友想要使…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...