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

P3029 [USACO11NOV]Cow Lineup S 双指针 单调队列

“五一”小长假来了趟上海,在倒数第二天终于有时间做了一会儿题目,A了之后过来写一篇题解

【问题描述】

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种,他喜欢他的照片包含每个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方, 每一头牛由一个整数位置 X_i以及整数品种编号 ID_i表示。

约翰想拍一张照片,这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当,这就意味着,在一系列照片中的最大和最小 X 坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本,这些照片中有每个不同的品种的至少一头牛,没有两头牛愿意站在同一个地点的。

【输入格式】

第 1 行:牛的数量 N;

第 2..1+N 行:每行包含 2 个以空格分隔的正整数 X_i 和 ID_i;意义如题目描述;

【输出格式】

输出共一行,包含每个不同品种 ID 的照片的最低成本。 

输入 #1
6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1 
输出 #1
4 

 --------------------------------------------------------------------------------------------------------------------------------

这题是我在学完单调队列、单调栈之后教练留的题目,但是我根本没用这两种(自己都觉得神奇)

题目说了每个牛有自己的位置和品种,想要照一张照片,照片必须涵盖所有品种的奶牛至少一头,然后照片长度还需要最短

也就是说:每个品种的奶牛都要尽量缩减数量

首先先把这些奶牛按照坐标升序排序,不然会很乱

题目中提示你:最大和最小 X 坐标的差距决定了照片的成本

只需要计算出最小的坐标和最大的坐标即可

算法整体大框架:

用两个变量表示现在的最小最大的坐标,分别命名为head,tail

因为我们要尽量减少每一种奶牛的数量,所以head和tail位置一定要是目前数量为1的牛,而head 和tail之间的🐮就管不了了

(macbook都没个像样的自带画图软件只能将就了

栗子🌰:

位置:1 2 3 5 8 10
品种:5 5 2 2 3 3head    tail

初始head为1,tail为n

首先,head位置和旁边都是5,既然要保留最少的个数,就把head++,吞掉第一个

目前,5品种的🐮只剩这一只了,不能再删了

来看tail这边,他旁边的和他是一个品种,只能无情把这个🐮删掉了,tail--

整个过程就是这样的,就是前后一直缩减,直到head和tail位置品种的🐮都是一个为止

把这些抽象成代码就很简单了:

注意⚠️:先缩减head和先缩减tail的结果也许是不一样的,所以得计算两次,最后取最小值

# include <iostream>
# include <cstdio>
# include <deque>
# include <algorithm>
# include <map>
using namespace std;
# define int long long
int n,head,tail;
struct node{int x,d;
}a[60005];
bool cmp(node a,node b){return a.x<b.x;
}
map <int,int> v;
map <int ,int> v1;
signed main(){scanf("%lld",&n);for (int i=1;i<=n;i++){scanf("%lld%lld",&a[i].x,&a[i].d);v[a[i].d]++;v1[a[i].d]++;}sort(a+1,a+1+n,cmp);head=1,tail=n;int first=0,second=0;while(v[a[tail].d]!=1){v[a[tail].d]-=1;tail--;}while(v[a[head].d]!=1){v[a[head].d]-=1;head++;}first=a[tail].x-a[head].x;head=1,tail=n;while(v1[a[head].d]!=1){v1[a[head].d]--;head++;}while(v1[a[tail].d]!=1){v1[a[tail].d]--;tail--;}second=a[tail].x-a[head].x;printf("%lld",min(first,second));return 0;
}

一道提高+的题就AC掉力,没用单调队列和单调栈也能完美解决

今天的讲解就到这里,下次再见!

(完结撒花!🎉 

相关文章:

P3029 [USACO11NOV]Cow Lineup S 双指针 单调队列

“五一”小长假来了趟上海&#xff0c;在倒数第二天终于有时间做了一会儿题目&#xff0c;A了之后过来写一篇题解 【问题描述】 农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种&#xff0c;他喜欢他的照片包含每个品种的至少一头牛。 约翰的牛都站在一条沿…...

数据结构与算法之链表: Leetcode 83. 删除排序链表中的重复元素 (Typescript版)

删除排序链表中的重复元素 https://leetcode.cn/problems/remove-duplicates-from-sorted-list/ 描述 给定一个已排序的链表的头 head &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 示例 1 输入&#xff1a;head [1,1,2] 输出&…...

ubuntu16.04升级到20.04后报错 By not providing “FindEigen.cmake“

编译问题&#xff1a; CMake Error at modules/perception/lidar/CMakeLists.txt:14 (find_package): By not providing "FindEigen.cmake" in CMAKE_MODULE_PATH this project has asked CMake to find a package configuration file provided by "Eigen&…...

设计模式——模板方法模式

是什么&#xff1f; 在我们的实际开发中尝尝会遇到这种问题&#xff1a;在设计一个系统时知道了算法所需要的关键步骤&#xff0c;而且确定了这些步骤的执行顺序&#xff0c;但是某些步骤的具体实现还不知道&#xff0c;或者说某些步骤的实现与具体的环境相关&#xff0c;例如每…...

15 | Qt的自定义信号

1 前提 Qt 5.14.2 2 具体操作 2.1 自定义信号 2.1.1 UI界面设置 2.1.1.1 widget.ui 2.1.1.2 setdialog.ui 2.1.2 headers 2.1.2.1 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget>QT_BEGIN_NAMESPACE namespace Ui {class Widget; } QT_END_NAMESP…...

线性表,顺序表,链表

线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列 线性表是一种在实际中广泛使 用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构&#xff0c;也就说是连续的一条直线 …...

洛谷 P2782 友好城市 线性DP 最长上升子序列 二分查找 lower_bound

&#x1f351; 算法题解专栏 &#x1f351; 洛谷&#xff1a;友好城市 题目描述 有一条横贯东西的大河&#xff0c;河有笔直的南北两岸&#xff0c;岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸&#xff0c;而且不同城市的友好城市不相同。每对…...

easyexcel读取excel合并单元格数据

普通的excel列表&#xff0c;easyexcel读取是没有什么问题的。但是&#xff0c;如果有合并单元格&#xff0c;那么它读取的时候&#xff0c;能获取数据&#xff0c;但是数据是不完整的。如下所示的单元格数据&#xff1a; 我们通过简单的异步读取&#xff0c;最后查看数据内容&…...

2023哪款蓝牙耳机性价比高?200左右高性价比蓝牙耳机推荐

现如今的蓝牙耳机越来越多&#xff0c;人们在选择时不免纠结&#xff0c;不知道选什么蓝牙耳机比较好&#xff1f;针对这个问题&#xff0c;我来给大家推荐几款性价比高的蓝牙耳机&#xff0c;一起来看看吧。 一、南卡小音舱Lite2蓝牙耳机 参考价&#xff1a;299 蓝牙版本&am…...

Java代码弱点与修复之——Masked Field(掩码字段)

弱点描述 MF: Masked Field (FB.MF_CLASS_MASKS_FIELD) 是 FindBugs 代码分析工具的一个警告信息, 属于中风险的代码弱点。 Masked Field,翻译过来是掩码字段, 字段可以理解为属性, 那么掩码是什么意思呢? 掩码是什么? 掩码是一串二进制代码对目标字段进行位与运算,屏…...

C语言编程入门之刷题篇(C语言130题)(8)

&#xff08;题目标题可以直接跳转此题链接&#xff09; BC72 平均身高 描述 从键盘输入5个人的身高&#xff08;米&#xff09;&#xff0c;求他们的平均身高&#xff08;米&#xff09;。 输入描述&#xff1a; 一行&#xff0c;连续输入5个身高&#xff08;范围0.00~2.00…...

QML动画类型总结

目录 一 常用动画 二 特殊场景动画 一 常用动画 有几种类型的动画&#xff0c;每一种都在特定情况下都有最佳的效果&#xff0c;下面列出了一些常用的动画&#xff1a; 1、PropertyAnimation&#xff08;属性动画&#xff09;- 使用属性值改变播放的动画&#xff1b; 2、Num…...

编译一个魔兽世界开源服务端Windows需要安装什么环境

编译一个魔兽世界开源服务端Windows需要安装什么环境 大家好我是艾西&#xff0c;去年十月份左右wy和bx发布了在停服的公告。当时不少小伙伴都在担心如果停服了怎么办&#xff0c;魔兽这游戏伴随着我们渡过了太多的时光。但已经发生的事情我们只能顺其自然的等待GF的消息就好了…...

HTML5字体集合的实践经验

随着互联网的发展&#xff0c;网站已成为人们获取信息和交流的重要平台。而一个好的网站&#xff0c;不仅需要有美观的界面&#xff0c;还需要有良好的用户体验。其中&#xff0c;字体是影响用户体验的一个重要因素。下面就让我们来看看HTML字体集合的相关内容。 HTML字体集合是…...

Mybatis 框架 ( 一 ) 基本步骤

1.概念 1.1.什么是Mybatis框架 &#xff08;1&#xff09;Mybatis是一个半ORM&#xff08;Object Relation Mapping 对象关系映射&#xff09;框架&#xff0c;它内部封装了JDBC&#xff0c;开发时只需要关注SQL语句本身&#xff0c;不需要花费精力去处理加载驱动、创建连接、…...

【华为OD机试真题】We Are A Team(C++javapython)100%通过率 超详细代码注释 代码优化

We Are A Team 题目描述: 总共有n个人在机房,每个人有一个标号(1<=标号<=n) ,他们分成了多个团队,需要你根据收到的m条消息判定指定的两个人是否在 一个团队中,具体的: 1、消息构成为abc,整数a、b分别代表两个人的标号,整数C代表指令 2、c = = 0 代表a和b在一…...

Oracle_Workflow_Builder工作流工具(一)

简介 目标WORKFLOW是oracle 公司的一个标准产品&#xff0c;它通过图形化的方式来表达业务处理过程。用户使用工作流可以灵活地定义或更改流程的结构。WORKFLOW是建立在数据库基础上的一个应用&#xff0c;它由后台的数据对象和前台的客户端程序组成。本文档主要介绍工作流的基…...

JavaWeb学习--RequestResponse

目录 JavaWeb学习--Request&Response 1&#xff0c;Request和Response的概述 request:获取请求数据 response:设置响应数据 **小结** 2&#xff0c;Request对象 **小结** 2.2 Request获取请求数据 **小结** 2.4 请求参数中文乱码问题 URL编码 2.5 Request请求转…...

Linux cat 命令

cat&#xff08;英文全拼&#xff1a;concatenate&#xff09;命令用于连接文件并打印到标准输出设备上。 使用权限 所有使用者 语法格式 cat [-AbeEnstTuv] [--help] [--version] fileName 参数说明&#xff1a; -n 或 --number&#xff1a;由 1 开始对所有输出的行数编…...

力扣sql中等篇练习(十四)

力扣sql中等篇练习(十四) 1 最后一个能进入电梯的人 1.1 题目内容 1.1.1 基本题目信息 1.1.2 示例输入输出 1.2 示例sql语句 # 在表某一个范围内的可以考虑自连接的方式,注意连接的表只需要精准的字段 # 需要排序是因为它需要找到最后一个上车的用户 SELECT q1.person_name…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

LeetCode - 394. 字符串解码

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

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...