算法日记————对顶堆(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大的数字,考虑使用两个优先队列,一个大9999999999根堆一个小根堆,小根堆维护大于等于第k大的数字的数,它的堆顶就是堆内最小,第k大的数字,另外一个大根堆维护小于等于k的数…...

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

unity3d for web
时光噶然 一晃好多年过去了(干了5年的u3d游戏),记得最后一次使用的版本好像是 unity 2017。 那个是 unity3d for webgl 还需要装个插件。用起来很蛋疼。 最近做一个小项目 在选择是用 Layabox 还是 cocosCreate 的时候 我想起了老战友 Uni…...
大宋咨询(深圳问卷调研)关于消费者研究的流程
消费者研究是一项至关重要的任务,它有助于企业了解目标市场的需求、偏好和行为,从而制定更加精准的营销策略。在执行消费者研究时,需要遵循一定的步骤和方法,以确保研究的准确性和有效性。开展消费者研究需要一系列的步骤和方法。…...

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

iOS - Runtime-isa详解(位域、union(共用体)、位运算)
文章目录 iOS - Runtime-isa详解(位域、union(共用体)、位运算)前言1. 位域介绍1.1 思路1.2 示例 - 结构体1.3 示例 - union(共用体)1.3.1 说明 1.4 结构体 对比 union(共用体) 2. a…...
使用VSCode搭建Vue 3开发环境
使用VSCode搭建Vue 3开发环境 Vue 3是一种流行的前端JavaScript框架,它提供了响应式的数据绑定和组合式的API。Visual Studio Code(VSCode)是一个轻量级但功能强大的源代码编辑器,支持多种语言开发。本文将引导您完成使用VSCode搭建Vue 3开发环境的步骤。 1. 下载和安装V…...

深度学习中的模型蒸馏技术:实现流程、作用及实践案例
在深度学习领域,模型压缩与部署是一项重要的研究课题,而模型蒸馏便是其中一种有效的方法。 模型蒸馏(Model Distillation)最初由Hinton等人在2015年提出,其核心思想是通过知识迁移的方式,将一个复杂的大模型…...

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

夜晚水闸3D可视化:科技魔法点亮水利新纪元
在宁静的夜晚,当城市的霓虹灯逐渐暗淡,你是否曾想过,那些默默守护着城市安全的水闸,在科技的魔力下,正焕发出别样的光彩?今天,就让我们一起走进夜晚水闸3D模型,感受科技为水利带来的…...

从零开始的软件开发实战:互联网医院APP搭建详解
今天,笔者将以“从零开始的软件开发实战:互联网医院APP搭建详解”为主题,深入探讨互联网医院APP的开发过程和关键技术。 第一步:需求分析和规划 互联网医院APP的主要功能包括在线挂号、医生预约、医疗咨询、健康档案管理等。我们…...
【深度学习】YOLO检测器的发展历程
YOLO检测器的发展历程 YOLO(You Only Look Once)检测器是一种流行的实时对象检测系统,以其速度和准确性而闻名。自2016年首次推出以来,YOLO已经成为计算机视觉领域的一个重要里程碑。在本博客中,我们将探讨YOLO检测器…...

C语言--编译和链接
1.翻译环境 计算机能够执行二进制指令,我们的电脑不会直接执行C语言代码,编译器把代码转换成二进制的指令; 我们在VS上面写下printf("hello world");这行代码的时候,经过翻译环境,生成可执行的exe文件&…...
实现使用C#代码完成wifi的切换和连接功能
实现使用C#代码完成wifi的切换和连接功能 代码如下: namespace Wifi连接器 {public partial class Form1 : Form{private List<Wlan.WlanAvailableNetwork> NetWorkList new List<Wlan.WlanAvailableNetwork>();private WlanClient.WlanInterface Wla…...

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

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

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

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

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

分享全栈开发医疗小程序 -带源码课件(课件无解压密码),自行速度保存
课程介绍 分享全栈开发医疗小程序 -带源码课件(课件无解压密码),自行速度保存!看到好多坛友都在求SpringBoot2.X Vue UniAPP,全栈开发医疗小程序 - 带源码课件,我看了一下,要么链接过期&…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&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 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

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

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...