当前位置: 首页 > 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的朋友想要使…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

云原生时代的系统设计:架构转型的战略支点

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、云原生的崛起&#xff1a;技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深&#xff0c;传统的 I…...

虚拟机网络不通的问题(这里以win10的问题为主,模式NAT)

当我们网关配置好了&#xff0c;DNS也配置好了&#xff0c;最后在虚拟机里还是无法访问百度的网址。 第一种情况&#xff1a; 我们先考虑一下&#xff0c;网关的IP是否和虚拟机编辑器里的IP一样不&#xff0c;如果不一样需要更改一下&#xff0c;因为我们访问百度需要从物理机…...