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

算法日记————对顶堆(4道题)

对顶堆的作用主要在于动态维护第k大的数字,考虑使用两个优先队列,一个大9999999999根堆一个小根堆,小根堆维护大于等于第k大的数字的数,它的堆顶就是堆内最小,第k大的数字,另外一个大根堆维护小于等于k的数字,堆顶是最大的,如此一来,就可以以排序的方式进行数字交换了

1.板子题 P7072 [CSP-J2020] 直播获奖

// Problem: 
//     P7072 [CSP-J2020] 直播获奖
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7072
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;int main(){int n,m;cin>>n>>m;priority_queue<int> a;//大根堆priority_queue<int,vector<int>,greater<int>> b;for(int i=1;i<=n;++i){int x;cin>>x;if(b.empty()||x>=b.top()) b.push(x);else a.push(x);int k=max(1,i*m/100);if(b.size()>k) a.push(b.top()),b.pop();if(b.size()<k) b.push(a.top()),a.pop();cout<<b.top()<<' ';}return 0;
}

2.中位数

不知道为啥开绿题,可能是没标签我就想不到用对顶堆

代码如下

// Problem: 
//     P1168 中位数
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1168
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
using namespace std;int main(){int n;cin>>n;priority_queue<int> a;priority_queue<int,vector<int>,greater<int>> b;for(int i=1;i<=n;++i){int x;cin>>x;if(b.empty()||x>b.top()) b.push(x);else a.push(x);if(i%2){int k=(i+1)/2;while(b.size()<k) b.push(a.top()),a.pop();while(b.size()>k) a.push(b.top()),b.pop();cout<<b.top()<<endl;}}return 0;
}

3.P1801 黑匣子

这道题反其行之,维护的是第k小,实际上是一样的,我们稍微想想就能发现,第k小的数字不就是大根堆的堆顶吗,稍微改一下代码就行。

这道题让我找到了对顶堆的局限性:动态查第k个数字,变化不能很大,否则就会TLE(限定)

// Problem: 
//     P1801 黑匣子
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1801
// Memory Limit: 500 MB
// Time Limit: 500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
#include<vector>
using namespace std;int main(){int n,m;cin>>n>>m;vector<int> a(n+2);vector<int> b(m+2);for(int i=1;i<=n;++i) cin>>a[i];for(int i=1;i<=m;++i) cin>>b[i];b[m+1]=1e9;priority_queue<int> c;priority_queue<int,vector<int>,greater<int>> d;int cnt=1,k=0;for(int i=1;i<=n;++i){if(c.empty()||a[i]<c.top()) c.push(a[i]);else d.push(a[i]);while(b[cnt]<=i){k++;cnt++;while(c.size()>k) d.push(c.top()),c.pop();while(c.size()<k) c.push(d.top()),d.pop();cout<<c.top()<<endl;} }
}

4.P2085 最小函数值

原本想了想,用偏暴力的方法AC了,结果发现原来是数据不好(

我的想法是到了一定大小,x方就会作为主力,

原代码如下(用n=1 m=10000就可以hack掉)

// Problem: 
//     P2085 最小函数值
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2085
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+10;int main(){priority_queue<int> a;priority_queue<int,vector<int>,greater<int>> b;int n,m;cin>>n>>m;for(int i=1;i<=n;++i){int x,y,z;cin>>x>>y>>z;for(int j=1;j<=500;++j){int k=x*j*j+y*j+z;if(a.empty()||k<=a.top()) a.push(k);else b.push(k);}}while(a.size()>m) b.push(a.top()),a.pop();while(a.size()<m) a.push(b.top()),b.pop();vector<int> c((int)a.size()+1);int len=a.size();for(int i=1;i<=len;++i){c[i]=a.top();a.pop();}for(int i=len;i>=1;--i){cout<<c[i]<<' ';}cout<<endl;return 0;	
}

这里有一种优化的方法,也就是加入了一个break,在一定次数后操作次数就会变得很少就会导致break掉。这里其实无需维护那个小根堆,直接维护大根堆即可,因为小根堆的作用是处理那个变化的m,这里的m是不变的

// Problem: 
//     P2085 最小函数值
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2085
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+10;int main(){priority_queue<int> a;int n,m;cin>>n>>m;for(int i=1;i<=n;++i){int x,y,z;cin>>x>>y>>z;for(int j=1;j<=m;++j){int k=x*j*j+y*j+z;if(a.size()<m) a.push(k);else{if(a.top()>k) a.push(k),a.pop();else break;}}}//while(a.size()>m) b.push(a.top()),a.pop();//while(a.size()<m) a.push(b.top()),b.pop();vector<int> c((int)a.size()+1);int len=a.size();for(int i=1;i<=len;++i){c[i]=a.top();a.pop();}for(int i=len;i>=1;--i){cout<<c[i]<<' ';}cout<<endl;return 0;	
}

相关文章:

算法日记————对顶堆(4道题)

对顶堆的作用主要在于动态维护第k大的数字&#xff0c;考虑使用两个优先队列&#xff0c;一个大9999999999根堆一个小根堆&#xff0c;小根堆维护大于等于第k大的数字的数&#xff0c;它的堆顶就是堆内最小&#xff0c;第k大的数字&#xff0c;另外一个大根堆维护小于等于k的数…...

【I.MX6ULL移植】Ubuntu-base根文件系统移植

1.下载Ubuntu16.04根文件系统 http://cdimage.ubuntu.com/ 1 2 3 4 5 2.解压ubuntu base 根文件系统 为了存放 ubuntu base 根文件系统&#xff0c;先在 PC 的 Ubuntu 系统中的 nfs 目录下创建一个名为 ubuntu_rootfs 的目录&#xff0c;命令如下&#xff1a; 【注意&…...

unity3d for web

时光噶然 一晃好多年过去了&#xff08;干了5年的u3d游戏&#xff09;&#xff0c;记得最后一次使用的版本好像是 unity 2017。 那个是 unity3d for webgl 还需要装个插件。用起来很蛋疼。 最近做一个小项目 在选择是用 Layabox 还是 cocosCreate 的时候 我想起了老战友 Uni…...

大宋咨询(深圳问卷调研)关于消费者研究的流程

消费者研究是一项至关重要的任务&#xff0c;它有助于企业了解目标市场的需求、偏好和行为&#xff0c;从而制定更加精准的营销策略。在执行消费者研究时&#xff0c;需要遵循一定的步骤和方法&#xff0c;以确保研究的准确性和有效性。开展消费者研究需要一系列的步骤和方法。…...

STM32看似无法唤醒的一种异常现象分析

1. 引言 STM32 G0 系列产品具有丰富的外设和强大的处理性能以及良好的低功耗特性&#xff0c;被广泛用于各类工业产品中&#xff0c;包括一些需要低功耗需求的应用。 2. 问题描述 用户使用 STM32G0B1 作为汽车多媒体音响控制器的控制芯片&#xff0c;用来作为收音机频道存贮…...

iOS - Runtime-isa详解(位域、union(共用体)、位运算)

文章目录 iOS - Runtime-isa详解&#xff08;位域、union&#xff08;共用体&#xff09;、位运算&#xff09;前言1. 位域介绍1.1 思路1.2 示例 - 结构体1.3 示例 - union&#xff08;共用体&#xff09;1.3.1 说明 1.4 结构体 对比 union&#xff08;共用体&#xff09; 2. a…...

使用VSCode搭建Vue 3开发环境

使用VSCode搭建Vue 3开发环境 Vue 3是一种流行的前端JavaScript框架,它提供了响应式的数据绑定和组合式的API。Visual Studio Code(VSCode)是一个轻量级但功能强大的源代码编辑器,支持多种语言开发。本文将引导您完成使用VSCode搭建Vue 3开发环境的步骤。 1. 下载和安装V…...

深度学习中的模型蒸馏技术:实现流程、作用及实践案例

在深度学习领域&#xff0c;模型压缩与部署是一项重要的研究课题&#xff0c;而模型蒸馏便是其中一种有效的方法。 模型蒸馏&#xff08;Model Distillation&#xff09;最初由Hinton等人在2015年提出&#xff0c;其核心思想是通过知识迁移的方式&#xff0c;将一个复杂的大模型…...

Java服务运行在Linux----维护常用命令

想起来哪些再添加上去 查看Java程序进程 jps -l 查出进程后根据pid 查询程序所在目录 pwdx 31313 根据端口查找PID 根据pid杀死程序 kill -p 31313 查看目录下所有包含9527的文件 grep -rn 9527 查看磁盘空间 查找文件名"nginx"文件或模糊查找"*nginx*&quo…...

夜晚水闸3D可视化:科技魔法点亮水利新纪元

在宁静的夜晚&#xff0c;当城市的霓虹灯逐渐暗淡&#xff0c;你是否曾想过&#xff0c;那些默默守护着城市安全的水闸&#xff0c;在科技的魔力下&#xff0c;正焕发出别样的光彩&#xff1f;今天&#xff0c;就让我们一起走进夜晚水闸3D模型&#xff0c;感受科技为水利带来的…...

从零开始的软件开发实战:互联网医院APP搭建详解

今天&#xff0c;笔者将以“从零开始的软件开发实战&#xff1a;互联网医院APP搭建详解”为主题&#xff0c;深入探讨互联网医院APP的开发过程和关键技术。 第一步&#xff1a;需求分析和规划 互联网医院APP的主要功能包括在线挂号、医生预约、医疗咨询、健康档案管理等。我们…...

【深度学习】YOLO检测器的发展历程

YOLO检测器的发展历程 YOLO&#xff08;You Only Look Once&#xff09;检测器是一种流行的实时对象检测系统&#xff0c;以其速度和准确性而闻名。自2016年首次推出以来&#xff0c;YOLO已经成为计算机视觉领域的一个重要里程碑。在本博客中&#xff0c;我们将探讨YOLO检测器…...

C语言--编译和链接

1.翻译环境 计算机能够执行二进制指令&#xff0c;我们的电脑不会直接执行C语言代码&#xff0c;编译器把代码转换成二进制的指令&#xff1b; 我们在VS上面写下printf("hello world");这行代码的时候&#xff0c;经过翻译环境&#xff0c;生成可执行的exe文件&…...

实现使用C#代码完成wifi的切换和连接功能

实现使用C#代码完成wifi的切换和连接功能 代码如下&#xff1a; namespace Wifi连接器 {public partial class Form1 : Form{private List<Wlan.WlanAvailableNetwork> NetWorkList new List<Wlan.WlanAvailableNetwork>();private WlanClient.WlanInterface Wla…...

Mac添加和关闭开机应用

文章目录 mac添加和关闭开机应用添加开机应用删除/查看 mac添加和关闭开机应用 添加开机应用 删除/查看 打开&#xff1a;系统设置–》通用–》登录项–》查看登录时打开列表 选中打开项目&#xff0c;点击“-”符号...

QT QInputDialog弹出消息框用法

使用QInputDialog类的静态方法来弹出对话框获取用户输入&#xff0c;缺点是不能自定义按钮的文字&#xff0c;默认为OK和Cancel&#xff1a; int main(int argc, char *argv[]) {QApplication a(argc, argv);bool isOK;QString text QInputDialog::getText(NULL, "Input …...

Unity3d使用Jenkins自动化打包(Windows)(一)

文章目录 前言一、安装JDK二、安装Jenkins三、Jenkins插件安装和使用基础操作 实战一基础操作 实战二 四、离线安装总结 前言 本篇旨在介绍基础的安装和操作流程&#xff0c;只需完成一次即可。后面的篇章将深入探讨如何利用Jenkins为Unity项目进行打包。 一、安装JDK 1、进入…...

HarmonyOS 应用开发之Want的定义与用途

Want 是一种对象&#xff0c;用于在应用组件之间传递信息。 其中&#xff0c;一种常见的使用场景是作为 startAbility() 方法的参数。例如&#xff0c;当UIAbilityA需要启动UIAbilityB并向UIAbilityB传递一些数据时&#xff0c;可以使用Want作为一个载体&#xff0c;将数据传递…...

enscan自动化主域名信息收集

enscan下载 Releases wgpsec/ENScan_GO (github.com) 能查的分类 实操&#xff1a; 首先打开linux 的虚拟机、 然后把下面这个粘贴到虚拟机中 解压后打开命令行 初始化 ./enscan-0.0.16-linux-amd64 -v 命令参数如下 oppo信息收集 运行下面代码时 先去配置文件把coo…...

分享全栈开发医疗小程序 -带源码课件(课件无解压密码),自行速度保存

课程介绍 分享全栈开发医疗小程序 -带源码课件&#xff08;课件无解压密码&#xff09;&#xff0c;自行速度保存&#xff01;看到好多坛友都在求SpringBoot2.X Vue UniAPP&#xff0c;全栈开发医疗小程序 - 带源码课件&#xff0c;我看了一下&#xff0c;要么链接过期&…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

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

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

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...