黑匣子——KEY

2024-02-04 12:18
文章标签 key 黑匣子

本文主要是介绍黑匣子——KEY,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

黑匣子

(box.pas/c/cpp)
【 问题描述】
某研究小组成员想发明一个黑匣子( 当然不是飞机上那个), 而是一个具有特殊功能
箱子。 这个箱子具有两个功能: 1. 存放一些正整数 x; 2. 对于第 k 次询问, 它会告
你箱子中第 k 小的数字是多少。 但光具有理论是不够的, 理论往往应联系实际。 这可是
个大大的难题, 没有丰富程序设计知识的同学们希望你能帮助他们写出这个程序代码, 以
他们能完成黑匣子的制作。
【 输入格式】
第一行, 一个数字 n 表示对黑匣子的操作次数。
以下 n 行, 每行一个数字。 若这个数字是正整数, 则表示在黑匣子中添加这个数字,
若这个数字是-­1, 这表示一次询问。
【 输出格式】
若干行, 对应每次询问所得的结果( 必定存在答案)
【 样例输入】
8 1 ­
-1
8 8 ­
-1
5 ­
-1
­-1
【 样例输出】
1
8
8
8
【 样例说明】
第一次询问时, 黑匣子内为 1, 输出最小的数 1;
第二次询问时, 黑匣子内为 1 8 8, 输出第二小的数 8;
第三次询问时, 黑匣子内为 1 5 8 8, 输出第三小的数 8;
第四次询问时, 黑匣子内为 1 5 8 8, 输出第四小的数 8。
【 数据范围】
对于30%的数据, 5<=n<=200
对于60%的数据, 5<=n<=10000
对于100%的数据, 5<=n<=100000, n为整数, x为不超过maxlongint的正整数。//膜拜Y’Ads,kmz

第一眼看到本题,就像到了排序。但是囿于数据范围,直接排序无法得到满分。
所以我们用堆来解决这道题。C++的queue库可以快速,便捷地为我们提供大根堆和小根堆。(注意小根堆的定义)
priority_queue<int,vector<int>,greater<int> >

那么我们应该如何实现呢?
首先,我们先开两个堆,一个大根堆,一个小根堆。每次输出(-1)时就将小根堆的top(堆顶)输出,并将小根堆top放入大根堆中,以保证地k小。
如果读入一个数,那就得进行判断,如果读入的x<大根堆top,则说明x为前k小的数,即此时第k小的数依旧为大根堆top(大根堆top就是k-1小的数),所以将x放入大根堆中,将大根堆top放入小根堆中。如果读入的x>大根堆的top,那就直接将x放入小根堆。
通过这些操作,就可以维护正确的k。下面是代码

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
int i,j,k,n,m,tot,ans;
priority_queue<int> bh;
priority_queue<int,vector<int>,greater<int> > sh;
int main()
{scanf("%d",&n);int x;for(int j=1;j<=n;j++){scanf("%d",&x);if(x==-1){printf("%d\n",sh.top());bh.push(sh.top());sh.pop();continue;}if(!bh.empty()){if(x<=bh.top()){sh.push(bh.top());bh.pop();bh.push(x);continue;}}sh.push(x);}return 0;
}

这篇关于黑匣子——KEY的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677471

相关文章

git ssh key相关

step1、进入.ssh文件夹   (windows下 下载git客户端)   cd ~/.ssh(windows mkdir ~/.ssh) step2、配置name和email git config --global user.name "你的名称"git config --global user.email "你的邮箱" step3、生成key ssh-keygen

DBeaver 连接 MySQL 报错 Public Key Retrieval is not allowed

DBeaver 连接 MySQL 报错 Public Key Retrieval is not allowed 文章目录 DBeaver 连接 MySQL 报错 Public Key Retrieval is not allowed问题解决办法 问题 使用 DBeaver 连接 MySQL 数据库的时候, 一直报错下面的错误 Public Key Retrieval is

为 Key-Value 数据库实现MVCC 事务

ACID是软件领域使用最广泛的技术之一,它是关系数据库的基石,是企业级中间件不可或缺的部分,但通常通过黑盒的方式提供。但是在许多情况下,这种古老的事务方式已经不能够适应现代大规模系统和NoSQL数据库的需要了,现代系统要求更高的性能要求,更大的数据量,更高的可用性。在这种情况下,传统的事务模型被定制的事务或者半事务模型所取代,而在这些模型中事务性并不像以往那样被看重。   在本文中我们会讨论一

【UE4 C++】使用自定义的结构体做TMap中的Key

使用UE4的TMap TMap是UE4中一个基础的容器类(在一些其他的场合也叫作“Dictionary”),表明了【键】-【值】一一对应的关系。 比如,我想统计一个场景中每个Actor出现的次数,就可以创建一个Map来存储信息: TMap<AActor*, int> testMap; 尝试在UE4中使用自定义的结构体作为【键】,编译失败 我自定义的结构体如下: struct Test

【蓝桥杯嵌入式(二)Led、Key、Lcd】

蓝桥杯嵌入式(二)Led、Key、Lcd 五、Led模块1.原理图配置2. 知识点3.底层代码 六、Key模块1.原理图配置2.知识点3.底层代码底层代码(四⾏代码版本)底层代码(状态机版本) 七、LCD模块1.原理图配置2.知识点底层代码 五、Led模块 1.原理图配置 2. 知识点 链接: 上拉电阻的通俗解释 链接: 单⽚机怎么输出⾼电平!推挽输出和开

【SpringBoot】96、SpringBoot中使用RedisTemplate的scan方法查找所有的key

1、简介 Redis Scan 命令用于迭代数据库中的数据库键。SCAN 命令是一个基于游标的迭代器,每次被调用之后, 都会向用户返回一个新的游标, 用户在下次迭代时需要使用这个新游标作为 SCAN 命令的游标参数, 以此来延续之前的迭代过程。SCAN 返回一个包含两个元素的数组, 第一个元素是用于进行下一次迭代的新游标, 而第二个元素则是一个数组, 这个数组中包含了所有被迭代的元素。如果新游标

redis 实现单位时间内错误记录 时间到key值就被清除------最近脑子不好使觉得还是写个博客试试

直接在客户端操作的, 所以需要redis的简单命令  去对比JAVA客户端jedis的命令就行   添加---set     格式 set  key  value  EX time(秒)   如果这个time不添加的话 ,那默认就是 永久 获取--get    格式 get key  ---查看剩余时间    格式 TTL key ---实现key实现自增: inrc key

ssh登录服务器报错“no matching host key type found. Their offer: ssh-rsa,ssh-dss”解决方法

这个错误表明你尝试使用 ssh 连接到远程服务器时,客户端和服务器之间没有匹配的 host key 类型。具体来说,远程服务器提供了 ssh-rsa 和 ssh-dss 类型的 host key,但你的 SSH 客户端配置可能不再支持这些较旧的算法。最近的 OpenSSH 版本默认禁用了不够安全的算法,如 ssh-rsa 和 ssh-dss。 解决方法 临时启用 ssh-rsa: 你可以在

github Host key verification failed

不是密钥问题,不是权限问题,只是在询问 (yes/no)的时候直接回车了,输入yes 再回车就ok了!

FUSEE: A Fully Memory-Disaggregated Key-Value Store——论文阅读

FAST 2023 Paper 论文阅读笔记整理 问题 分布式内存键值(KV)存储正在采用分离式内存(DM)体系结构以提高资源利用率。然而,现有的DM上的KV存储采用半分离式设计,在DM上存储KV对,但在单个元数据服务器上管理元数据,因此仍然在元数据服务器上遭受低资源效率的问题。 如图1a,Clover[60]采用半分离式设计,在计算节点(CN)上部署客户端,在内存节点(MN)上存储KV对,