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

牛客14666(优先屏障) + 牛客14847(Masha与老鼠)

文章目录

  • 写在前面
  • 14666-优先屏障
    • 思路
    • 编程
  • 14847-Masha与老鼠
    • 思路
    • 编程

写在前面

昨天刷的这两道题写了很久·····,特别是Masha与老鼠这道题,写了都快3个小时,主要还是理解代码逻辑有点难,不过写完之后感觉收获挺大的,给我以后刷题提供很好的思路

14666-优先屏障

思路

考点:单调栈+前缀后缀模拟
我们先不考虑屏障的位置,先考虑某个点往前面看和往后面看监视的总个数,很容易想到前缀和后缀的思路,在此之前先说栈的用处,栈用来存放每次遍历过的山的高度,先说前缀的思路,从头遍历,每次先加上前面监视的个数,判断当前栈顶元素是否小于当前元素,如果小于将栈顶排除,计数器+1(如果当前元素的高度大于栈顶元素,那么之后的山都看不到栈顶元素的山,所以直接将他排出去),如果栈为空,加上计数器,反之加上计数器的同时在+1(当前的山和栈顶的山可以相互监视),然后再将当前元素进栈,后缀同理,然后再从头遍历,由于加完屏障左边的只能看前面,右边的只能看后面,所以考虑前缀[i-1]和后缀[i]相加最小值即可

编程

const int N=5e4+5;
int a[N],qz[N],hz[N];
int num=1;
void solve(){memset(hz,0,sizeof hz);stack<int> st; int n;cin >> n;for(int i=1;i<=n;++i) cin >> a[i];for(int i=1;i<=n;++i){int sum=0;qz[i]=qz[i-1];while(!st.empty() && st.top()<a[i]){//判断是否需要排除栈顶元素sum++;st.pop(); }if(st.empty()) qz[i]+=sum;//栈为空加上计数器else qz[i]+=sum+1;//不为空加上计数器在加上本身st.push(a[i]);}while(!st.empty()) st.pop();for(int i=n;i>=1;--i){int sum=0;hz[i]=hz[i+1];while(!st.empty() && st.top()<a[i]){sum++;st.pop(); }if(st.empty()) hz[i]+=sum;else hz[i]+=sum+1;st.push(a[i]);}int maxn=0,k=0;int mx=qz[n];//总的监视个数for(int i=1;i<=n;++i){if(mx-(qz[i-1]+hz[i])>maxn){//前缀和后缀相加的值最小maxn=mx-(qz[i-1]+hz[i]);k=i;}}cout << "Case #" << num++ << ": " << k << " " << maxn << endl;return ;
}

14847-Masha与老鼠

思路

考点:贪心+反悔贪心
根据贪心策略,每只老鼠有两个选择,左边最近的有容量的洞,右边最近的有容量的洞

  • 优先队列q1存老鼠,q2存洞,按坐标大小出队。老鼠存的值为-k-x,洞存的值为-x,x为该点坐标,k为偏差值。

输入一个洞-鼠-洞-鼠-洞样例,仔细观察。当鼠2进洞2时,鼠1的位置被挤掉,那么鼠1就会回到上一个状态,k值算的就是所有现状态回到上一个状态时的偏差值的累加,即ans += k,就能让ans回到上一个状态。
讲起来比较抽象,具体看代码

编程

const int N=2e6+50;
PII p[N];
priority_queue<int,vector<int>,greater<int>> q1;//存老鼠
priority_queue<PII,vector<PII>,greater<PII>> q2;//存洞,用pair存洞的位置和下标
void solve(){int n,m;cin >> n >> m;int sum=n;int ans=0;for(int i=1;i<=n;++i) cin >> p[i].fi;for(int i=1;i<=m;++i){cin >> p[i+n].fi >> p[i+n].se;sum-=p[i+n].se;}n+=m;if(sum>0){//无解只要判断洞的总数小于老鼠总数即可cout << -1 << endl;return ;}sort(p+1,p+1+n);//将老鼠和洞的位置按升序排序for(int i=1;i<=n;++i){int x=p[i].fi;if(p[i].se){//洞while(p[i].se && !q1.empty() && x+q1.top()<0){//将q1.top展开,x1-x2<k,意思为当前坐标减去老鼠坐标小于之前他们的差值int k=x+q1.top();ans+=k;//加上差值q1.pop();--p[i].se;q2.push({-k-x,0});//提供反悔次数,如果后边的老鼠进入当前这个洞,则会将当前老鼠挤回前面那个洞,这里-k为这个老鼠进入这个洞和进入前面那个洞之间的差值}if(p[i].se){--p[i].se;q2.push({-x,i});}}else{//老鼠int k=INT_MAX;//先将k定义为一个超出1e9范围的数,如果外面没洞的话优先考虑这只老鼠if(!q2.empty()){//外面有洞int j=q2.top().se;k=x+q2.top().fi;//k为洞和老鼠位置的差值q2.pop();if(p[j].se){--p[j].se;q2.push({-p[j].fi,j});}}ans+=k;//加上差值q1.push(-k-x);//存入-k-x具体看上面}}cout << ans << endl;return ;
}

相关文章:

牛客14666(优先屏障) + 牛客14847(Masha与老鼠)

文章目录 写在前面14666-优先屏障思路编程 14847-Masha与老鼠思路编程 写在前面 昨天刷的这两道题写了很久&#xff0c;特别是Masha与老鼠这道题&#xff0c;写了都快3个小时&#xff0c;主要还是理解代码逻辑有点难&#xff0c;不过写完之后感觉收获挺大的&#xff0c;给我以…...

Git下载与安装

下载网址&#xff1a;https://git-scm.com/downloads 下载之后开始安装 选择安装路径&#xff0c;next 选择需要安装的组件&#xff0c;这里默认即可&#xff0c;next 选择菜单文件夹&#xff0c;这里默认即可&#xff0c;next 选择默认编辑器&#xff0c;默认推荐的即可&…...

创建vue2/vue3项目

目录 创建一个Vue2项目创建一个Vue3项目 创建一个Vue2项目 ## 安装Vue-Cli &#xff1a; npm install -g vue/cli // Vue CLI 4.x 需要 Node.js v8.9 或更高版本 (推荐 v10 以上)vue --version // 检测版本是否正确## 创建一个项目&#xff1a; vue create hello-world // hel…...

IOS七层模型对应的网络协议和物理设备

以下是网络模型、对应的协议以及对应的物理设备的表格总结&#xff1a; 网络模型层次主要功能对应协议对应物理设备物理层透明的传输比特流&#xff0c;确定机械及电气规范RS-232、V.35、RJ-45、FDDI等中继器、集线器、网线、调制解调器、网卡数据链路层将比特组装成帧和点到点…...

论文复现:Predictive Control of Networked Multiagent Systems via Cloud Computing

Predictive Control of Networked Multiagent Systems via Cloud Computing论文复现 文章目录 Predictive Control of Networked Multiagent Systems via Cloud Computing论文复现论文摘要系统参数初始化系统模型观测器预测过程控制器设计系统的整体框图仿真结果 论文摘要 翻译…...

JSON 文件存储

JSON 全称为&#xff1a; JavaScript Object Notation 也就是 javaScript 对象标记&#xff0c;通过对象和数组的组合来表示数据&#xff0c; 虽然构造简洁&#xff0c;但是结构化程度非常高&#xff0c; 是一种轻量级的数据交换格式 对象和数组 在 JavaScript 语言中&#…...

python——pynput

pynput 是一个 Python 库&#xff0c;用于控制和监听键盘与鼠标输入。它在 Windows、macOS 和 Linux 上都可以工作&#xff0c;为用户提供了一个跨平台的输入事件处理方式。pynput 包含两个主要模块&#xff1a;keyboard 和 mouse&#xff0c;分别用于处理键盘和鼠标事件。 主…...

[用AI日进斗金系列]用码上飞在企微接单开发一个项目管理系统!

今天是【日进斗金】系列的第二期文章。 先给不了解这个系列的朋友们介绍一下&#xff0c;在这个系列的文章中&#xff0c;我们将会在企微的工作台的“需求发布页面”中寻找有软件开发需求的用户 并通过自研的L4级自动化智能软件开发平台「码上飞CodeFlying」让AI生成应用以解…...

《JavaEE篇》--多线程(2)

《JavaEE篇》--多线程(1) 线程安全 线程不安全 我们先来观察一个线程不安全的案例&#xff1a; public class Demo {private static int count 0;public static void main(String[] args) throws InterruptedException {Thread t1 new Thread(() -> {//让count自增5W次…...

防爆智能手机如何助力电气行业保驾护航?

在电气行业的智能化转型浪潮中&#xff0c;防爆智能手机以其强大的数据处理能力、实时通讯功能及高度集成的安全特性&#xff0c;正成为保障电力网络稳定运行、预防安全隐患的得力助手。 防爆智能手机在电气行业中发挥着重要的保驾护航作用&#xff0c;主要体现在以下几个方面&…...

24.7.24数组|那几个课后得做的题

1、对长整形数据进行反转 2、对字符串进行反转 一、题目地址&#xff1a; 1. 实现一个函数atoi&#xff0c;使其能够将字符串转换整数 (Leetcode 8/中等). - 力扣&#xff08;LeetCode&#xff09; 2. 颠倒给定的32位无符号整数的二进制位&#xff08;Leetcode 190/简单&…...

03Spring底层架构核心概念解析

为了感谢罕哥对我工作的帮助&#xff0c;特此记录下学习过程&#xff0c;期待成为和罕哥一样优秀的人 时间&#xff1a;2024.7.13 内容&#xff1a;spring源码课程3学习记录 一、BeanDefinition BeanDefinition表示Bean的定义&#xff0c;BeanDefinition中存在很多属性用来…...

Vue学习---vue 防抖处理函数,是处理什么场景

Vue防抖处理函数是用来处理在快速连续操作中&#xff0c;只执行最后一次操作的情况。 例如&#xff0c;在输入框输入时&#xff0c;我们可能希望只在用户完成输入后进行处理&#xff0c;而不是在每次键入时都处理。(n秒后触发一次) 以下是一个简单的Vue防抖处理函数的例子&am…...

力扣爆刷第166天之TOP100五连刷96-100(单词拆分、回溯、旋转数组)

力扣爆刷第166天之TOP100五连刷96-100&#xff08;单词拆分、回溯、旋转数组&#xff09; 文章目录 力扣爆刷第166天之TOP100五连刷96-100&#xff08;单词拆分、回溯、旋转数组&#xff09;一、24. 两两交换链表中的节点二、139. 单词拆分三、560. 和为 K 的子数组四、209. 长…...

2024在线PHP加密网站源码

源码介绍 2024在线PHP加密网站源码 更新内容: 1.加强算法强度 2.优化模版UI 加密后的代码示例截图 源码下载 https://download.csdn.net/download/huayula/89568335...

网络驱动移植(RTL8189)

1、把驱动放到内核文件夹中&#xff08;linux/drivers/net/wireless&#xff09;&#xff0c;对应的驱动可以在网上下载 2、修改该目录下的Kconfig和Makefile文件 3、配置内核&#xff08;make menuconfig&#xff09; 配置支持IEEE 802.11&#xff0c;选中8189模块&#xff0…...

go语言中map学习

在 Go 语言中,map 是一种引用类型,这意味着它有以下特点: 内存结构: map 实际上是一个指向底层数据结构的指针。这个底层数据结构包含键值对的集合。 赋值与传参: 当你给一个变量赋值一个 map 时,或者将 map 作为函数参数传递时,实际上传递的是指针,而不是完整的数据结构副本。…...

【C#】| 与 及其相关例子

按位或&#xff08;|&#xff09; 按位或运算符 | 对两个数的每一位进行比较&#xff0c;如果两个数中至少有一个为 1&#xff0c;则结果位为 1&#xff1b;否则&#xff0c;结果位为0。 1010 (10 in decimal) | 1100 (12 in decimal) ------1110 (14 in decimal) 力扣相关…...

【数据结构 | 哈希表】一文了解哈希表(散列表)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…...

go创建对象数组

在 Go 语言中&#xff0c;可以使用字面量的方式创建结构体对象数组。以下是一个示例代码&#xff0c;展示了如何使用字面量创建一个结构体对象数组&#xff1a; package mainimport "fmt"// 定义一个结构体 type Person struct {Name stringAge intAddress Address…...

5个技巧让Markdown Viewer成为你的浏览器文档中心

5个技巧让Markdown Viewer成为你的浏览器文档中心 【免费下载链接】markdown-viewer Markdown Viewer / Browser Extension 项目地址: https://gitcode.com/gh_mirrors/ma/markdown-viewer 还在为浏览器无法直接预览Markdown文档而烦恼吗&#xff1f;Markdown Viewer浏览…...

通义千问3-Reranker-0.6B性能调优:提升推理速度的3种方法

通义千问3-Reranker-0.6B性能调优&#xff1a;提升推理速度的3种方法 1. 引言 如果你正在使用通义千问3-Reranker-0.6B模型&#xff0c;可能会遇到推理速度不够理想的情况。特别是在处理大量文本排序任务时&#xff0c;等待时间可能会影响整体工作效率。 其实&#xff0c;这…...

九齐单片机NYIDE开发环境避坑指南:从仿真器到实物板的温度检测实战(以062E为例)

九齐单片机NYIDE开发环境避坑指南&#xff1a;从仿真器到实物板的温度检测实战&#xff08;以062E为例&#xff09; 在嵌入式开发领域&#xff0c;仿真环境与实物硬件之间的差异常常成为工程师的"隐形杀手"。特别是对于九齐单片机这类资源紧凑型芯片&#xff0c;开发…...

DeepSeek-OCR-2实战教程:OCR结果JSON Schema解析与结构化数据入库指南

DeepSeek-OCR-2实战教程&#xff1a;OCR结果JSON Schema解析与结构化数据入库指南 1. 项目简介 DeepSeek-OCR-2是基于深度学习的智能文档解析工具&#xff0c;专门针对结构化文档内容提取而设计。与传统的OCR工具只能提取纯文本不同&#xff0c;这个工具能够精准识别文档的排…...

OpenClaw+百川2-13B:个人知识库自动整理与问答系统搭建

OpenClaw百川2-13B&#xff1a;个人知识库自动整理与问答系统搭建 1. 为什么需要本地化知识管理系统 去年整理博士论文资料时&#xff0c;我遇到了一个典型的研究者困境&#xff1a;电脑里堆积了237个PDF、643篇网页存档和无数零散的笔记片段&#xff0c;但需要引用某个概念时…...

泛微OA单点登录配置全攻略:从零开始实现第三方系统免密登录

泛微OA单点登录深度实战&#xff1a;Token机制与系统集成最佳实践 对于企业IT架构师和运维团队而言&#xff0c;系统间的无缝衔接一直是提升工作效率的关键。想象一下这样的场景&#xff1a;销售人员在CRM系统中完成客户跟进后&#xff0c;无需反复登录就能直接跳转到OA系统提…...

Teensy41嵌入式FTP服务器库:轻量协议栈与多网络适配

1. 项目概述FTP_Server_Teensy41 是一款专为 Teensy 4.x 系列微控制器&#xff08;特别是 Teensy 4.0 和 Teensy 4.1&#xff09;深度定制的嵌入式 FTP 服务器库。它并非从零构建&#xff0c;而是基于 Jean-Michel Gallego 开发的成熟开源项目 Arduino-Ftp-Server 进行了系统性…...

如何彻底告别微软Edge浏览器:EdgeRemover专业卸载工具完全指南

如何彻底告别微软Edge浏览器&#xff1a;EdgeRemover专业卸载工具完全指南 【免费下载链接】EdgeRemover PowerShell script to remove Microsoft Edge in a non-forceful manner. 项目地址: https://gitcode.com/gh_mirrors/ed/EdgeRemover 你是否曾经尝试卸载Microsof…...

别再手动写RTL了!用Vivado FIR Compiler IP核5分钟搞定一个低通滤波器

5分钟极速部署&#xff1a;用Vivado FIR Compiler IP核实现专业级低通滤波器 在FPGA信号处理领域&#xff0c;滤波器设计往往需要耗费工程师大量时间在RTL编码和验证上。但今天&#xff0c;我们将颠覆这一传统工作流程——通过Vivado的FIR Compiler IP核&#xff0c;即使没有深…...

快充、便携、安全兼备,Anker能量盒到底香不香?

随着无线互联网时代的到来&#xff0c;移动设备的续航问题成为人们的新烦恼。无论是频繁出差、旅行&#xff0c;还是移动办公&#xff0c;充电宝几乎已经成为随身必备的装备。 然而&#xff0c;传统充电宝往往存在充电速度慢、体积笨重、功能单一&#xff0c;甚至安全认证不完善…...