当前位置: 首页 > 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…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...