洛谷网站: 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 坐标从小到大的排列。排序的时间复杂度是 ,这也是整个算法得主要时间开销之一。
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 题解
题目传送门: P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前言: 这道题的核心问题是在一条直线上分布着不同品种的牛,要找出一个连续区间,使得这个区间内包含所有不同品种的牛,…...

编程领域的IO模型(BIO,NIO,AIO)
目前对于市面上绝大多数的应用来说,不能实现的业务功能太少了。更多的是对底层细节,性能优化的追求。其中IO就是性能优化中很重要的一环。Redis快,mysql缓冲区存在的意义。都跟IO有着密切关系。IO其实我们都在用,输入输出流这块。…...
DeepSeek和ChatGPT的对比
最近DeepSeek大放异彩,两者之间有什么差异呢?根据了解到的信息,简单做了一个对比。 DeepSeek 和 ChatGPT 是两种不同的自然语言处理(NLP)模型架构,尽管它们都基于 Transformer 架构,但在设计目标…...
Pyqt 的QTableWidget组件
QTableWidget 是 PyQt6 中的一个表格控件,用于显示和编辑二维表格数据。它继承自 QTableView,提供了更简单的方式来处理表格数据,适合用于需要展示结构化数据的场景。 1. 常用方法 1.1 构造函数 QTableWidget(parent: QWidget None)&#x…...
4. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--什么是微服务--微服务设计原则与最佳实践
相比传统的单体应用,微服务架构通过将大型系统拆分成多个独立的小服务,不仅提升了系统的灵活性和扩展性,也带来了许多设计和运维上的挑战。如何在设计和实现微服务的过程中遵循一系列原则和最佳实践,从而构建一个稳定、高效、易维…...

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

树和二叉树_7
树和二叉树_7 一、leetcode-102二、题解1.引库2.代码 一、leetcode-102 二叉树的层序遍历 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 样例输入:root [3,9,20,null,nu…...
不同标签页、iframe或者worker之间的广播通信——BroadcastChannel
BroadcastChannel是一个现代浏览器提供的 API,用于在同一浏览器的不同浏览上下文(如不同的标签页、iframe 或者 worker)之间进行消息传递。它允许你创建一个广播频道,通过该频道可以在不同的浏览上下文之间发送和接收消息。 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:LED 闪烁 功能描述:通过操作 P1 口寄存器,让连接在 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 年,华为 P20 系列首次搭载 5 通道色温传感器,可帮助手机在不同光照条件下保持画面色彩一致性。 2020 年,华为 P40 系列搭载 8 通道多光谱色温传感器(实际为 11 通道,当时只用 8 个通道检测可见光)&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判断的性能困局
【前言】 本文将以哈希表重构实战为核心,完整展示如何将传统条件匹配逻辑(上千层if-else判断)转化为O(1)的哈希表高效实现。通过指纹验证场景的代码级解剖,您将深入理解: 1.哈希函数设计如何规避冲突陷阱 2.链式寻址法的工程实现…...

视频采集卡接口
采集卡的正面有MIC IN、LINE IN以及AUDIO OUT三个接口, MIC IN为麦克风输入,我们如果要给采集到的视频实时配音或者是在直播的时候进行讲解,就可以在这里插入一个麦克风, LINE IN为音频线路输入,可以外接播放背景音乐…...
蓝桥杯真题 - 像素放置 - 题解
题目链接:https://www.lanqiao.cn/problems/3508/learning/ 个人评价:难度 3 星(满星:5) 前置知识:深度优先搜索 整体思路 深搜,在搜索过程中进行剪枝,剪枝有以下限制条件…...
vue基础(三)
常用指令 1. v-bind 固定绑定与动态绑定: 语法: 标准语法:v-bind:属性"动态数据" 简写语法::属性"动态数拓" <!DOCTYPE html> <html lang"en"><head><me…...

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

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

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

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...

springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 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技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)
Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

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