P1878 舞蹈课（详解）c++
题目链接：P1878 舞蹈课 - 洛谷 | 计算机科学教育新生态
1.题目解析
1：我们可以发现任意两个相邻的都是异性，所以他们的舞蹈技术差值我们都要考虑，4和2的差值是2，2和4的差值是2，4和3的差值是1，根据题目找到1这个最小差值后，输出这一对舞伴的编号即下标3和4，再输出队列里面还剩的另一队舞伴的编号1和2，这里成功出列了两对舞伴，所以先输出总对数2再输出3 4再输出1 2
2.算法原理
解法：利用小根堆存所有相邻异性的差值，然后每次拿出最小的即可
举个例子，把全部相邻异性的差值算出来之后，拿最小的差值，此时最小的差值是2，根据题目如果不止一对，那么最左边的那一对出列，所以让2号3号舞伴出列，接着继续让下一个差值最小的舞伴出列，这个想法很正确，就是利用堆存放相邻异性的差值，然后每次拿出最小的就行了，但是这个想法会很多问题
1.取出相邻的一对异性之后，他们的左右，有可能变成新的一对
比如现在让最小差值为2的一对舞伴出列，原来在他们左边的男生和右边的女生会组成一对新的舞伴，如何能做到快速地删除完一个之后，还能把左右两个连接起来呢，就可以利用双向链表存队列
比如2和4舞伴出列后，让10指向7，7指向10就可以得到一个新队列，利用双向链表存队列，就可以实现删除一对舞伴后，只需修改指针，就可以快速地确定另一个，并且把新的队列还原出来
2.堆中，有可能存在已经出列的人
堆中存放这5个差值8 2 3 2 8，最小差值为2的一对舞伴出列后，1号和4号舞伴产生新的差值3，并把它放到堆里，2号，3号舞伴出列后，8和3就变成了无效元素，但它们还在堆里，此时我拿出3，再输出下标，就有可能出错，所以要杜绝这种情况，创建一个bool数组标记一下即可；true表示出列，false表示没出列，假如我把3拿出来，再判断他对应的舞伴3和4是否有出列的情况，如果有就不对这个3进行处理
3.堆中存什么？
我们要知道技术差以及左边的人是谁以及右边的人是谁，<技术差，左编号，右编号>，这样就能还原双向链表，把技术差拿到，知道左编号和右编号，通过修改指针就可以还原
代码
//舞蹈课
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>using namespace std;const int N = 2e5 + 10;int n;
int s[N]; //标记男女 - 1/0//双向链表存数据
//数据是从左向右依次进来的，4的右边就是2，2的左边就是4，
//直接把它定义出来就行了,就不需要h，id这些指针了
int e[N];
int pre[N], ne[N];struct node {int d; //技术差int l, r; //左右编号//小根堆，大元素下坠 bool operator <(const node& x) const{//根据题目如果不止一对，那么最左边的那一对出列//可以知道技术差有可能相等，所以技术差相等的时候可以根据左编号定义小根堆if (d != x.d) return d > x.d;else return l > x.l;}
};priority_queue<node> heap;
bool st[N]; //标记已经出列的人int main()
{cin >> n; for (int i = 1; i <= n; ++i){char ch; cin >> ch;if (ch == 'B') s[i] = 1;}for (int i = 1; i <= n; ++i){cin >> e[i];//直接创建双向链表pre[i] = i - 1;ne[i] = i + 1;}ne[n] = 0; //0表示后面没有元素//1.先把所有的异性放进堆里for (int i = 2; i <= n; ++i){//如果当前性别和前一个人的性别不一样if (s[i] != s[i - 1]){heap.push({ abs(e[i] - e[i - 1]), i - 1, i });}}//2.提取结果//我们最后要先输出有多少对出列，所以要先把结果存起来vector<node> ret; //暂存结果//堆里还要异性就一直出列while (heap.size()){node t = heap.top(); heap.pop();int d = t.d, l = t.l, r = t.r;//l、r其中任何一个标记ture，说明对应的位置里有人已经出列了if (st[l] || st[r]) continue;ret.push_back(t);st[l] = st[r] = true; //标记l或r已经出列//维护双向链表ne[pre[l]] = ne[r];pre[ne[r]] = pre[l];//判断新的左右是否会成为一对，左和右有可能不存在，判断异性就无意义//如果l的编号是1，1的左边是不存在人的，所以也要判断l/r是否存在int left = pre[l], right = ne[r];if (left && right && s[left] != s[right]){heap.push({ abs(e[left] - e[right]), left, right });}}cout << ret.size() << endl; for (auto& x : ret){cout << x.l << " " << x.r << endl;}return 0;
}也可以用pair存结果
//暂存结果vector<pair<int, int>> ret;//模拟出列过程while (heap.size()){node t = heap.top(); heap.pop();int d = t.d, l = t.l, r = t.r;if (st[l] || st[r]) continue; //对应舞伴已出列则不处理//记录结果ret.push_back({ l,r }); st[l] = st[r] = true; //标记已出列//更新双向链表int left = pre[l], right = ne[r];ne[left] = right;pre[right] = left;//检查新的相邻是否为异性组合//l和r如果是1或者n，那便没有左边人或右边人if (left && right && s[left] != s[right]){heap.push({ abs(e[left] - e[right]), left , right });}}cout << ret.size() << endl;for (auto& x : ret){cout << x.first << " " << x.second << endl;}相关文章：
P1878 舞蹈课（详解）c++
题目链接：P1878 舞蹈课 - 洛谷 | 计算机科学教育新生态 1.题目解析 1：我们可以发现任意两个相邻的都是异性，所以他们的舞蹈技术差值我们都要考虑，4和2的差值是2，2和4的差值是2，4和3的差值是1，根…...
或非门组成的SR锁存器真值表相关问题
PS：主要是给大家抛砖引玉，不喜勿喷。 问题描述：或非门组成的SR锁存器，为什么当SD和RD等于0时候的真值表一个是Q0，Q0.一个结果是Q1，Q1？...
机器学习算法 - 随机森林之决策树初探（1）
随机森林是基于集体智慧的一个机器学习算法，也是目前最好的机器学习算法之一。 随机森林实际是一堆决策树的组合（正如其名，树多了就是森林了）。在用于分类一个新变量时，相关的检测数据提交给构建好的每个分类树。每个…...
webpack构建流程
文章目录 [TOC](文章目录) 运行流程初始化流程编译构建流程compile编译make 编译模块build module 完成模块编译 输出流程seal输出资源emit输出完成 小结 运行流程 是一个串行的过程，它的工作流程就是将各个插件串联起来 在运行过程中会广播事件，插件只…...
服务器之连接简介（Detailed Explanation of Server Connection）
一台服务器最大能支持多少连接？一台客户端机器最多能发起多少条连接？？ 我们知道TCP连接，从根本上看其实就是client和server端在内存中维护的一组【socket内核对象】（这里也对应着TCP四元组：源IP、源端口、…...
第1章大型互联网公司的基础架构——1.5 服务发现
讲到这里，我们已经对一个客户端请求进入业务HTTP服务的过程有了较为详细的了解。业务HTTP服务在处理请求的过程中免不了与其他下游服务通信——可能会调用其他业务服务，可能需要访问数据库，可能会向消息中间件投递消息等，所以业务…...
uniapp PDF 预览和下载
创建 index.vue <template><view><view class"box"><view class"item" ><view class"title"><span></span><text>文件</text></view><view class"list" v-for"(…...
ubuntu服务器部署
关闭欢迎消息 服务器安装好 ubuntu 系统后，进行终端登录，会显示出很多的欢迎消息 通过在用户的根目录下执行 touch .hushlogin 命令，再次登录终端就不会出现欢迎消息 修改hostname显示 修改 /etc/hostname 文件内容为主机名，保…...
Deepseek 本地部署
准备环境 设备：家用笔记本电脑，8核/16G/1Tb SSD/无独显 系统：windows10 软件环境（非源码部署不需要）：conda 4.8.5、python3.7、git2.13 步骤 下载安装Ollama 下载地址：OllamaGet up and r…...
[Linux][问题处理]修改密码报You must wait longer to change your password
一、问题描述 在Linux控制台中修改密码，键入旧密码，设置并确认新密码后，却提示You must wait longer to change your password（您必须等待更长时间才能更改密码） 二、原因 当前修改时间 < Minimum number of da…...
《刚刚问世》系列初窥篇-Java+Playwright自动化测试-22- 操作鼠标拖拽 - 下篇（详细教程）
1.简介 上一篇中，宏哥说的宏哥在最后提到网站的反爬虫机制，那么宏哥在自己本地做一个网页，没有那个反爬虫的机制，谷歌浏览器是不是就可以验证成功了，宏哥就想验证一下自己想法，其次有人私信宏哥说是有那种…...
SpringBoot3使用Swagger3
版本 springboot3.4.2 JAVA 17 一、引入Swagger3依赖 <dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-starter-webmvc-ui</artifactId><version>2.0.4</version> </dependency> 二、快速启…...
HCIA综合项目之多技术的综合应用实验
十五 HCIA综合实验 15.1 IP规划 #内网分配网段192.168.1.0 24#内网包括骨干链路和两个用户网段，素以需要划分三个，借两位就够用了192.168.1.0 26--骨干192.168.1.64 26---R1下网络192.168.1.128 26---R2下网络192.168.1.192 26--备用192.168.1.64 26--…...
燕千云ITSM已支持DeepSeek对接！AI能力持续升级
春节期间，DeepSeek火爆全网，引发热议，作为国产AI大模型的黑马，DeepSeek凭借独特的训练方法、先进的模型架构和强大的联网推理能力，正不断拓展AI技术的应用边界。其“快思考”能力，可在极短时间内完成复杂决…...
Windows 自动主题：Windows AutoTheme
Windows 自动主题：Windows AutoTheme 链接：https://pan.xunlei.com/s/VOJ2ZG5t8QjL7_fGVIBgyxJQA1?pwdgbie# 自动切换：根据日出、日落时间自动切换 Windows 主题模式。高效轻量：使用 Rust 提供高效的系统调用，保证运…...
自定义Spring Cloud Gateway过滤器：记录慢请求
在构建微服务架构时，API网关是一个关键组件，它负责路由、负载均衡、安全验证等多种功能。Spring Cloud Gateway提供了强大的扩展能力，允许开发者通过自定义过滤器来增强其功能。本文将详细介绍如何实现一个自定义过滤器，用于记录响…...
python 浅拷贝和深拷贝
浅拷贝（Shallow Copy）语法示例代码 1示例代码 2 深拷贝（Deep Copy）语法示例代码 浅拷贝与深拷贝的区别示例：浅拷贝与深拷贝的对比 浅拷贝：只复制外层容器，内层嵌套对象仍然是共享的，…...
uni-app 学习（一）
一、环境搭建和运行 （一）创建项目 直接进行创建 （二）项目结构理解 pages 是页面 静态资源 打包文件，看我们想输出成什么格式 app.vue 页面的入口文件 main.js 是项目的入口文件 存放对打包文件的配置 pages 存放整…...
unity学习37：新版的动画器：动画状态机 Animator
目录 1 给游戏物体添加，新版的动画器 Animator 2 关于 Animator 3 创建 动画器的控制器 Animator Controller 4 打开动画编辑器 Animator 5 动画编辑器 还是Animation 5.1 创建新的动画 5.2 创建第2个动画 5.3 测试2个动画均可用 6 再次打开动画编辑器 A…...
FFmpeg+SDL实现简易视频播放器
参考链接 https://blog.csdn.net/qq_26611129/article/details/98732561 https://www.cnblogs.com/Azion/p/17756274.html https://avmedia.0voice.com/?id49050 https://blog.csdn.net/qq_44825209/article/details/133760652 https://www.cnblogs.com/Azion/p/17525955.htm…...
Vue3实现优雅的前端版本更新提示
背景 在前端项目开发中,当我们发布了新版本后,需要及时通知用户刷新页面以获取最新代码。本文将介绍一种优雅的实现方案。 实现原理 在项目根目录维护一个version.json文件,记录当前版本号前端定期请求version.json检查版本对比本地存储的版本号,如有更新则提示用户 核心代…...
vim常用快捷键
正常模式 在打开文件进入 Vim 后，默认处于正常模式，该模式下的快捷键主要用于光标移动、文本操作等。 光标移动 基本移动：h（左移）、j（下移）、k（上移）、l（右移…...
P1226 【模板】快速幂
P1226 【模板】快速幂 题目描述 给你三个整数 a , b , p a,b,p a,b,p，求 a b m o d p a^b \bmod p abmodp。 输入格式 输入只有一行三个整数，分别代表 a , b , p a,b,p a,b,p。 输出格式 输出一行一个字符串 a^b mod ps，其中 a , b…...
【gRPC-gateway】是否有拦截器的情况添加健康检查的细节，与多路复用runtime.NewServeMux和gRPC区别讲解，与跨域功能，go案例
健康检查详解 什么是健康检查？ 健康检查（Health Checking）是一种机制，用于监控服务的状态，确保服务在运行时是健康的、可用的。通过健康检查，系统可以自动检测服务是否正常工作，并在出现问题时…...
vue开发时，用localStorage常用方法及存储数组方法。
localStorage 可以让你在浏览器中存储键值对，并且在页面关闭后数据依然保留。localStorage 中存储的数据会一直保存在客户端，直到被手动删除或者清除浏览器缓存。 localStorage 中存储的数据在同一浏览器的不同窗口之间是共享的，而 sessionSt…...
HashMap详解+简单手写实现（哈希表）
1. 什么是 HashMap？ HashMap是Java集合框架中的一种数据结构，它实现了Map接口，用于存储键值对（Key-Value Pair）。HashMap允许null键和null值，并且不保证元素的顺序。 --- 2. HashMap 的工作原理 2.1 内…...
解决Did not find dashscope_api_key问题——jupyter设置环境变量
jupyter中使用通义千文langchain 报错 Value error, Did not find dashscope_api_key, please add an environment variable DASHSCOPE_API_KEY which contains it, or pass dashscope_api_key as a named parameter.我本来以为这样就是已经加上了： #导入相关包 i…...
尚硅谷爬虫note003
一、函数 1. 函数的定义 def 函数名（）： 代码 2.函数的调用 函数名（） 3. 定义参数（不调用函数不执行） def sum（a，b） #形参 c a b print（c&…...
算法兵法全略（译文）
目录 始计篇 谋攻篇 军形篇 兵势篇 虚实篇 军争篇 九变篇 行军篇 地形篇 九地篇 火攻篇 用间篇 始计篇 算法，在当今时代，犹如国家关键的战略武器，也是处理各类事务的核心枢纽。算法的世界神秘且变化万千，不够贤能聪慧…...
)
NO.17十六届蓝桥杯备战|do-while循环|break和continue语句|三道练习(C++)
do-while循环 do-while语法形式 在循环语句中 do while 语句的使⽤最少，它的语法如下： //形式1 do 语句; while( 表达式 );//形式2 do { 语句1; 语句2; ... } while( 表达式 );while 和 for 这两种循环都是先判断，条件如果…...
)
【广州大学主办，发表有保障 | IEEE出版，稳定EI检索，往届见刊后快至1个月检索】第二届电气技术与自动化工程国际学术会议 (ETAE 2025)
第二届电气技术与自动化工程国际学术会议 (ETAE 2025) The 2nd International Conference on Electrical Technology and Automation Engineering 大会官网：http://www.icetae.com/【更多详情】 会议时间：2025年4月25-27日 会议地点：…...
Spring Cache 详细讲解
Spring Cache 是 Spring 框架提供的缓存抽象层，通过统一的 API 和注解简化缓存操作，支持多种缓存实现（如 Redis、EhCache、Caffeine 等）。其核心目标是减少重复计算，提升系统性能，同时保持代码简洁性。 1. …...
CPT205 计算机图形学 OpenGL 3D实践（CW2）
文章目录 1. 介绍2. 设计3. 准备阶段4. 角色构建5. 场景构建6. 交互部分6.1 键盘交互6.2 鼠标交互6.3 鼠标点击出多级菜单进行交互 7. 缺点与问题7.1 程序bug7.2 游戏乐趣不足7.3 画面不够好看 8. 完整代码 1. 介绍 前面已经分享过了关于CPT205的CW1的2D作业，这次C…...
Netty的基本架构详解
EventLoopGroup基本认识 我们需要了解的 EventLoopGroup, Netty对EventLoopGroup做了很多的扩展实现，下图是他的家族图谱： 我们上一节课使用的案例，使用的是NioEventLoopGroup，他是NIO的实现，可以看出来他是Multithre…...
2025前端面试题超全面解析（附答案与深度扩展）
文章目录 一、HTML篇（扩展版）1. **HTML5语义化标签的实际应用场景**2. **Web Components实战：如何封装一个自定义按钮组件？**3. **Web Worker的用途与限制** 二、CSS篇（扩展版）1. **CSS盒模型详解ÿ…...
自己搭建可以和deepseek对话的WEB应用
第一步 下载安装anaconda，地址：https://repo.anaconda.com/ 第二步 打开anaconda客户端，打开conda命令行窗口 第三步 创建一个open-webui专属的python专属的虚拟环境，并且指定python具体的版本 conda create --name open…...
Linux系统运行模式和链接
一、系统运行模式 centos6 0 关机模式 1 单用户模式 2 字符模式，无网络连接 3 字符模式 4 预留 5 图形模式 6 重启模式 查看系统当前处于的运行模式 切换为图形模式 init 5 centos7 字符模式 multi-user…...
.NET 9.0 的 Blazor Web App 项目，进度条 ＜progress＞ 组件使用注意事项
一、执行过程中，要刷新 进度条 的显示，需要 延时、释放，否则进度条不 实时 更新，最后一下到 100% // 延时，释放给前端：【必须】，否则进度条不 实时 更新，最后一下到 100await Task.D…...
头歌实验--面向对象程序设计
目录 实验五 类的继承与派生 第1关：简易商品系统 任务描述 答案代码 第2关：公司支出计算 任务描述 答案代码 第3关：棱柱体问题 任务描述 答案代码 实验五 类的继承与派生 第1关：简易商品系统 任务描述 答案代码 #incl…...
IoTDB 断电后无法启动 DataNode，日志提示 Meet error while starting up
问题 IoTDB 1.3.2 版本，断电后 IoTDB 的 DataNode 无法启动，日志如下： 2024-12-16 14:45:41,350 [main] ERROR o.a.i.db.service.DataNode:562 - Meet error while starting up. org.apache.iotdb.commons.exception.StartupException: Fo…...
-E卷B卷-100分)
2024华为OD机试真题-最大报酬(C++)-E卷B卷-100分
2024华为OD机试最新题库-(C卷+D卷+E卷)-(JAVA、Python、C++) 目录 题目描述 输入描述 输出描述 示例一 解题思路 考点 代码 c++ 题目描述 小明每周上班都会拿到自己的工作清单，工作清单内包含n项工作， 每项工作都有对应的耗时时间（单位h）和报酬, 工作的总报酬为…...
jenkins war Windows安装
Windows安装Jenkins 需求1.下载jenkins.war2.编写快速运行脚本3.启动Jenkins4.Jenkins使用 需求 1.支持在Windows下便捷运行Jenkins； 2.支持自定义启动参数； 3.有快速运行的脚步样板。 1.下载jenkins.war Jenkins下载地址：https://get.j…...
HCIA项目实践--RIP相关原理知识面试问题总结回答
9.4 RIP 9.4.1 补充概念 什么是邻居？ 邻居指的是在网络拓扑结构中与某一节点（如路由器）直接相连的其他节点。它们之间可以直接进行通信和数据交互，能互相交换路由信息等，以实现网络中的数据转发和路径选择等功能。&am…...
用大模型学大模型04-模型与网络
目前已经学完深度学习的数学基础，开始学习各种 模型和网络阶段，给出一个从简单到入门的，层层递进的学习路线。并给出学习每种模型需要的前置知识。增加注意力机制，bert, 大模型，gpt, transformer， MOE等流行…...
浏览器扩展实现网址自动替换
作为一个开发爱好者，不能顺畅访问github是很痛苦的，这种状况不知道何时能彻底解决。 目前也有很多方案可以对应这种囧况，我此前知道有一个网站kkgithub，基本上把github的静态内容都搬了过来，我们如果需要访问某个githu…...
适配器模式详解（Java）
一、引言 1.1 定义与类型 适配器模式是一种结构型设计模式，主要目的是将一个类的接口转换为客户期望的另一个接口。这种模式使得原本因为接口不匹配而不能一起工作的类可以一起工作，从而提高了类的复用性。适配器模式分为类适配器和对象适配器两种类型。类适配器使用继承关…...
C语言表驱动法
最近了解到一种C语言的写法，故记录下来，内容来自deepseek。 表驱动法 表驱动法（Table-Driven Approach）是一种编程技术，通过使用表格（数组、结构体数组、哈希表等）来存储数据或逻辑࿰…...
【鸿蒙Next】优秀鸿蒙博客集锦
鸿蒙基础开发：多文件压缩上传及断点续传_鸿蒙 断点续传-CSDN博客...
Django REST Framework：如何获取序列化后的ID
Django REST Framework：如何获取序列化后的ID 😄 嗨，小伙伴们！今天我们来聊一聊Django REST Framework（简称DRF）中一个非常常见的操作：如何获取序列化后的ID。对于那些刚入门的朋友们ÿ…...
deep seek
1.介绍:DeepSeek是一款由国内人工智能公司研发的大型语言模型，拥有强大的自然语言处理能力，能够理解并回答问题，还能辅助写代码、整理资料和解决复杂的数学问题。免费开源，媲美ChatGPT 最近最火爆的AI对话程序。 www.deepseek.com…...