当前位置: 首页 > 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;要么链接过期&…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

LeetCode - 394. 字符串解码

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

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

轻量级Docker管理工具Docker Switchboard

简介 什么是 Docker Switchboard &#xff1f; Docker Switchboard 是一个轻量级的 Web 应用程序&#xff0c;用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器&#xff0c;使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...