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

洛谷网站: P3029 [USACO11NOV] Cow Lineup S 题解

题目传送门:

P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言:

这道题的核心问题是在一条直线上分布着不同品种的牛,要找出一个连续区间,使得这个区间内包含所有不同品种的牛,并且这个区间的成本(即区间内牛的最大和最小 x 坐标之差)最小。整体来说是非常的简单易手。

#思路概括:

        我们将采用滑动窗口算法来解决这个问题。滑动窗口算法是一种在数组或序列上通过维护两个指针(通常称为左指针和右指针)来动态调整窗口大小,从而解决各种子区间相关问题的有效方法。在本题中,我们会利用这个算法不断尝试不同的连续区间,找出满足条件的最小成本区间。

##实现具体步骤:

        1、数据读取与品种的统计:

                1.1、首先,我们读取输入的牛的数量 N。

                1.2、接着,使用一个循环读取每头牛的 x 坐标 和品种 ID ,并将其存储在一个结果体数组当中。

                1.3、同时,我们使用一个哈希表,来记录每个品种的出现情况。在遍历牛的信息时,将每个品种添加剂道哈希表当中,这样咱们就能统计出不同品种的总数。

        2、排序操作:

                我们为了方便实用华东窗口算法,我们需要按照牛的 x 坐标对所有牛进行排序。通过自定义比较函数,可以确保牛按照 x 坐标从小到大的排列。排序的时间复杂度是  o(n log n),这也是整个算法得主要时间开销之一。

        3、滑动窗口初始化:

                1.1、初始化两个指针 left 和 right 都指向这排序后数组的第一个元素,它们分别代表着滑动窗口的左右边界。

                1.2、初始化cb为0,这用于记录当前窗口内不同品种的数量;初始化 m 为 INT_MAX,用于存储满足条件的最小成本。

        4、滑动窗口操作:

                1.1、扩大窗口:

                        不多移动 right 指针,将新的牛加入道窗口当中。

                        检查新加入的牛的品种在当前窗口内的数量,如果该品种之前在窗口内的数量为0,说明这是一个新的品种,将 cb 加上1。

                        同时更新该品种在窗口内的数量。

        5、缩小窗口:

                当 right  指针遍历完所有牛后,m 中存储的就是满足条件的最小成本,将其输出即可。

###复杂度分析:

        1、时间复杂度:

                排序操作的时间复杂度为 O(n log n),滑动遍历数组的时间复杂度为 O(n),因此总的时间复杂度是 O(n log n)。

        2、空间复杂度:

                主要的空间开销在于存储牛的信息和哈希表,哈希值最多存储 k 个不同的品种,因此空间复杂度为 O(k)。

####代码:

#include<bits/stdc++.h>
using namespace std;
struct c {int x;int r;c(int x, int r) : x(x), r(r) {}
};
// 自定义比较函数,按照 x 坐标对牛进行排序
bool C(const c& a, const c& b) {return a.x < b.x;
}
int main() {int n;cin >> n;vector<c> o;unordered_map<int, int> bc;// 读取输入并存储牛的信息for (int i = 0; i < n; ++i) {int x, r;cin >> x >> r;o.emplace_back(x, r);bc[r] = 0;}// 统计不同品种的数量int u = bc.size();// 按照 x 坐标对牛进行排序sort(o.begin(), o.end(), C);int l = 0, r = 0;int cb = 0;int m = INT_MAX;// 滑动窗口while (r < n) {// 扩大窗口if (bc[o[r].r] == 0) {++cb;}++bc[o[r].r];// 当窗口内包含了所有不同品种的牛时,尝试缩小窗口while (cb == u) {m = min(m, o[r].x - o[l].x);--bc[o[l].r];if (bc[o[l].r] == 0) {--cb;}++l;}++r;}cout << m << endl;return 0;
}

相关文章:

洛谷网站: P3029 [USACO11NOV] Cow Lineup S 题解

题目传送门&#xff1a; P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前言&#xff1a; 这道题的核心问题是在一条直线上分布着不同品种的牛&#xff0c;要找出一个连续区间&#xff0c;使得这个区间内包含所有不同品种的牛&#xff0c;…...

编程领域的IO模型(BIO,NIO,AIO)

目前对于市面上绝大多数的应用来说&#xff0c;不能实现的业务功能太少了。更多的是对底层细节&#xff0c;性能优化的追求。其中IO就是性能优化中很重要的一环。Redis快&#xff0c;mysql缓冲区存在的意义。都跟IO有着密切关系。IO其实我们都在用&#xff0c;输入输出流这块。…...

DeepSeek和ChatGPT的对比

最近DeepSeek大放异彩&#xff0c;两者之间有什么差异呢&#xff1f;根据了解到的信息&#xff0c;简单做了一个对比。 DeepSeek 和 ChatGPT 是两种不同的自然语言处理&#xff08;NLP&#xff09;模型架构&#xff0c;尽管它们都基于 Transformer 架构&#xff0c;但在设计目标…...

Pyqt 的QTableWidget组件

QTableWidget 是 PyQt6 中的一个表格控件&#xff0c;用于显示和编辑二维表格数据。它继承自 QTableView&#xff0c;提供了更简单的方式来处理表格数据&#xff0c;适合用于需要展示结构化数据的场景。 1. 常用方法 1.1 构造函数 QTableWidget(parent: QWidget None)&#x…...

4. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--什么是微服务--微服务设计原则与最佳实践

相比传统的单体应用&#xff0c;微服务架构通过将大型系统拆分成多个独立的小服务&#xff0c;不仅提升了系统的灵活性和扩展性&#xff0c;也带来了许多设计和运维上的挑战。如何在设计和实现微服务的过程中遵循一系列原则和最佳实践&#xff0c;从而构建一个稳定、高效、易维…...

网络安全威胁框架与入侵分析模型概述

引言 “网络安全攻防的本质是人与人之间的对抗&#xff0c;每一次入侵背后都有一个实体&#xff08;个人或组织&#xff09;”。这一经典观点概括了网络攻防的深层本质。无论是APT&#xff08;高级持续性威胁&#xff09;攻击、零日漏洞利用&#xff0c;还是简单的钓鱼攻击&am…...

树和二叉树_7

树和二叉树_7 一、leetcode-102二、题解1.引库2.代码 一、leetcode-102 二叉树的层序遍历 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 样例输入&#xff1a;root [3,9,20,null,nu…...

不同标签页、iframe或者worker之间的广播通信——BroadcastChannel

BroadcastChannel是一个现代浏览器提供的 API&#xff0c;用于在同一浏览器的不同浏览上下文&#xff08;如不同的标签页、iframe 或者 worker&#xff09;之间进行消息传递。它允许你创建一个广播频道&#xff0c;通过该频道可以在不同的浏览上下文之间发送和接收消息。 Broa…...

开源CodeGPT + DeepSeek-R1 是否可以替代商业付费代码辅助工具

开源CodeGPT + DeepSeek-R1 是否可以替代商业付费代码辅助工具 背景与研究目的 在快速发展的软件开发领域,代码辅助工具已成为提高开发效率和质量的关键。然而,商业付费工具如通义灵码和腾讯AI代码助手,尽管功能强大,但其高昂的成本和许可证限制,使得许多企业寻求更具吸…...

AUTOSAR汽车电子嵌入式编程精讲300篇-基于FPGA的CAN FD汽车总线数据交互系统设计

目录 前言 汽车总线以及发展趋势 汽车总线技术 汽车总线发展趋势 CAN FD总线国内外研究现状 2 系统方案及CAN FD协议分析 2.1系统控制方案设计 2.2 CAN FD总线帧结构分析 2.2.1数据帧分析 2.2.2远程帧分析 2.2.3过载帧分析 2.2.4错误帧分析 2.2.5帧间隔分析 2.3位…...

STC51案例操作

案例 1&#xff1a;LED 闪烁 功能描述&#xff1a;通过操作 P1 口寄存器&#xff0c;让连接在 P1.0 引脚的 LED 以一定间隔闪烁。 #include <reg51.h>// 延时函数 void delay(unsigned int time) {unsigned int i, j;for (i 0; i < time; i)for (j 0; j < 123; …...

多光谱技术在华为手机上的应用发展历史

2018 年&#xff0c;华为 P20 系列首次搭载 5 通道色温传感器&#xff0c;可帮助手机在不同光照条件下保持画面色彩一致性。 2020 年&#xff0c;华为 P40 系列搭载 8 通道多光谱色温传感器&#xff08;实际为 11 通道&#xff0c;当时只用 8 个通道检测可见光&#xff09;&am…...

C语言:函数栈帧的创建和销毁

目录 1.什么是函数栈帧2.理解函数栈帧能解决什么问题3.函数栈帧的创建和销毁的过程解析3.1 什么是栈3.2 认识相关寄存器和汇编指令3.3 解析函数栈帧的创建和销毁过程3.3.1 准备环境3.3.2 函数的调用堆栈3.3.3 转到反汇编3.3.4 函数栈帧的创建和销毁 1.什么是函数栈帧 在写C语言…...

NLP_[2]_文本预处理-文本数据分析

文章目录 4 文本数据分析1 文件数据分析介绍2 数据集说明3 获取标签数量分布4 获取句子长度分布5 获取正负样本长度散点分布6 获取不同词汇总数统计7 获取训练集高频形容词词云8 小结 4 文本数据分析 学习目标 了解文本数据分析的作用.掌握常用的几种文本数据分析方法. 1 文…...

【工具篇】深度揭秘 Midjourney:开启 AI 图像创作新时代

家人们,今天咱必须好好唠唠 Midjourney 这个在 AI 图像生成领域超火的工具!现在 AI 技术发展得那叫一个快,各种工具层出不穷,Midjourney 绝对是其中的明星产品。不管你是专业的设计师、插画师,还是像咱这种对艺术创作有点小兴趣的小白,Midjourney 都能给你带来超多惊喜,…...

从O(k*n)到O(1):如何用哈希表终结多层if判断的性能困局

【前言】   本文将以哈希表重构实战为核心&#xff0c;完整展示如何将传统条件匹配逻辑(上千层if-else判断)转化为O(1)的哈希表高效实现。通过指纹验证场景的代码级解剖&#xff0c;您将深入理解&#xff1a;   1.哈希函数设计如何规避冲突陷阱   2.链式寻址法的工程实现…...

视频采集卡接口

采集卡的正面有MIC IN、LINE IN以及AUDIO OUT三个接口&#xff0c; MIC IN为麦克风输入&#xff0c;我们如果要给采集到的视频实时配音或者是在直播的时候进行讲解&#xff0c;就可以在这里插入一个麦克风&#xff0c; LINE IN为音频线路输入&#xff0c;可以外接播放背景音乐…...

蓝桥杯真题 - 像素放置 - 题解

题目链接&#xff1a;https://www.lanqiao.cn/problems/3508/learning/ 个人评价&#xff1a;难度 3 星&#xff08;满星&#xff1a;5&#xff09; 前置知识&#xff1a;深度优先搜索 整体思路 深搜&#xff0c;在搜索过程中进行剪枝&#xff0c;剪枝有以下限制条件&#xf…...

vue基础(三)

常用指令 1. v-bind 固定绑定与动态绑定&#xff1a; 语法&#xff1a; 标准语法&#xff1a;v-bind:属性"动态数据" 简写语法&#xff1a;:属性"动态数拓" <!DOCTYPE html> <html lang"en"><head><me…...

使用Python开发PPTX压缩工具

引言 在日常办公中&#xff0c;PPT文件往往因为图片过大而导致文件体积过大&#xff0c;不便于传输和存储。为了应对这一问题&#xff0c;我们可以使用Python的wxPython图形界面库结合python-pptx和Pillow&#xff0c;开发一个简单的PPTX压缩工具。本文将详细介绍如何实现这一…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能

vxe-table vue 表格复选框多选数据&#xff0c;实现快捷键 Shift 批量选择功能 查看官网&#xff1a;https://vxetable.cn 效果 代码 通过 checkbox-config.isShift 启用批量选中,启用后按住快捷键和鼠标批量选取 <template><div><vxe-grid v-bind"gri…...