洛谷网站: 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压缩工具。本文将详细介绍如何实现这一…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
