思维+差分,CF 1884C - Medium Design
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
1884C - Medium Design
二、解题报告
1、思路分析
考虑 最大值 和 最小值的位置 mai, mii
对于 一个 包含 mai 的线段,我们选择:
如果 该线段包含 mii,答案不会变大
如果 该线段不包含 mii,答案会 + 1
也就是说,对于所有的包含 mai 的线段,我们拿进来不会使得答案变差
同时包含 mai,mii 的线段我们可以不拿
那么我们说明 最优解 的 mii 一定在 两端
我们按照 mii 在左端 和 右端 的情况分别计算,求最值即可
以mii = 0为例,我们对于所有左端点不为0的线段按左右端点双关键字排序,跑差分
维护被覆盖次数最多的点的次数,维护最值即可
2、复杂度
时间复杂度: O(nlogn)空间复杂度:O(n)
3、代码详解
#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {int n, m;std::cin >> n >> m;std::vector<int> l(n), r(n);for (int i = 0; i < n; ++ i) {std::cin >> l[i] >> r[i];-- l[i];}std::vector<std::pair<int, int>> segs;for (int i = 0; i < n; ++ i) {if (l[i] > 0) {segs.emplace_back(l[i], 1);segs.emplace_back(r[i], -1);}}int ans = 0;int cur = 0, lst = 0;std::ranges::sort(segs);for (auto &[x, y] : segs) {if (x > lst) {ans = std::max(ans, cur);}lst = x; cur += y;}if (m > lst) {ans = std::max(ans, cur);}segs.clear();for (int i = 0; i < n; ++ i) {if (r[i] < m) {segs.emplace_back(l[i], 1);segs.emplace_back(r[i], -1);}}std::ranges::sort(segs);cur = 0, lst = 0;for (auto &[x, y] : segs) {if (x > lst) {ans = std::max(ans, cur);}lst = x;cur += y;}if (m > lst) {ans = std::max(ans, cur);}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint add = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - add << '\n';
#endifreturn 0;
}
相关文章:

思维+差分,CF 1884C - Medium Design
目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 1884C - Medium Design 二、解题报告 1、思路分析 考虑 最大值 和 最小值…...

简单介绍冯诺依曼体系
现代的计算机, 大多遵守冯诺依曼体系结构 CPU中央处理器:进行算术运算和逻辑判断。存储器:分为外存和内存,用于存储数据(使用二进制方式存储)。输入设备:用户给计算机发号施令。输出设备:计算机…...

kernel32.dll下载地址:如何安全地恢复系统文件
关于从网络上寻找kernel32.dll的下载地址,这通常不是一个安全的做法,而且可能涉及到多种风险。kernel32.dll是Windows操作系统的核心组件之一,负责内存管理、进程和线程管理以及其他关键系统功能。因为kernel32.dll是系统的基础文件ÿ…...
【高等数学】多元微分学 (一)
偏导数 偏导数定义 如果二元函数 f f f 在 x 0 , y 0 x_0,y_0 x0,y0 的某邻域有定义, 且下述极限存在 lim Δ x → 0 f ( x 0 Δ x , y 0 ) − f ( x 0 , y 0 ) Δ x \lim_{\Delta x\to 0} \frac{f(x_0\Delta x,y_0)-f(x_0,y_0)}{\Delta x} Δx→0limΔxf(x0Δ…...

Python爬取京东商品信息,详细讲解,手把手教学(附源码)
Python 爬虫爬取京东商品信息 下面我将逐一解释每一部分的代码 导入库 from selenium import webdriver from selenium.webdriver.edge.service import Service from selenium.webdriver.edge.options import Options import time import random import csv from selenium.c…...

大家有没有了解过TLKS-PLGS这款接地电阻在线监测装置?它在电力系统中能发挥什么作用呢?
接地电阻在线监测仪(输电铁塔接地电阻监测装置、变电站接地电阻监测装置、三极法接地网电阻监测装置)在电力系统中发挥着至关重要的作用,具体来说,有以下几个方面: 一、实时监测预警。该装置采用激励脉冲技术…...

Shell中的函数
目录 一、系统函数 (一)前言 (二)常用的函数 basename [string/pathname] [suffix] 二、自定义函数 (一)语法 (二)脚本例子 三、函数实际案例 过程中的报错: …...

通过IP地址或者主机名添加打印机20241023
文印室打印机连接方式20241023 Win键盘搜索打印机和扫描仪点击添加打印机或扫描仪,等候片刻点击“我需要的打印机不在列表中”添加打印机,选择使用IP地址或主机名添加打印机点击下一步,设备类型选择自动检测输入主机名:即打印机有…...

基于SpringBoot+Vue智慧养老关爱系统【提供源码+答辩PPT+参考文档+项目部署】
💥 这两年毕业设计和毕业答辩的要求和难度不断提升,传统的JavaWeb项目缺少创新和亮点,往往达不到毕业答辩的要求! ❗如何解决这类问题? 让我们能够顺利通过毕业,我也一直在不断思考、努力、精进。通过2024年…...

新手教学系列——利用短效代理快速搭建代理池
引言 在进行高并发数据抓取时,很多人都会遇到频繁IP被封的问题。要解决这个问题,代理池的搭建就成了关键。通过频繁更换代理IP,我们可以绕过网站的反爬机制,提升抓取效率。然而,很多初学者可能会觉得构建一个健壮的代理池颇为复杂,尤其是需要快速切换的短效代理池。在这…...
实体与DTO如何转换
下面是一些常用的转换库: Dozer 该项目目前不活跃,并且很可能在未来被弃用。 ModelMapper 一个智能对象映射库,可自动将对象相互映射。它采用基于约定的方法,同时提供简单、重构安全的应用程序接口(API)来…...

Docker 安装Postgres和PostGIS,并制作镜像
1. 查找postgres和postgis现有的镜像和版本号 镜像搜索网站:https://docker.aityp.com/ 测试使用的是postgres:15.4 和 postgis:15-3.4 2、镜像拉取 docker pull postgres:15.4docker pull postgis/postgis:15-3.4镜像下载完成,docker images 查看如…...

ES6:let和const命令解读以及变量的解构赋值
有时候,我们需要的不是答案,而是一双倾听的耳朵 文章目录 let和const命令变量的解构赋值 let和const命令 let和const命令都是声明变量的关键字,类同varlet特点 用来声明变量,不能再次定义,但是值可以改变存在块级作用…...
java-collection集合整理0.9.4
java-集合整理0.9.0 基本结构基本概念实例化举例遍历获取指定值 2024年10月17日09:43:16–0.9.0 2024年10月18日11:00:59—0.9.4 基本结构 Collection 是最顶级的接口。分为 List 和 Set 两大类。List 分为:ArrayList、LinkedList、Vector。Set 分为:Ha…...

ParallelsDesktop20最新版本虚拟机 一键切换系统 游戏娱乐两不误
让工作生活更高效:Parallels Desktop 20最新版本虚拟机的神奇之处 大家好!👋 今天我要跟大家安利一款让我工作效率飞升的神器——Parallels Desktop 20最新版本虚拟机。作为一个日常需要在不同操作系统间来回穿梭的人,这款软件简直…...
现代C语言:C23标准重大更新
虽然没有固定标准,但一般将C99之后的C语言标准称为“现代C语言”,目前的最新标准为C23。C语言的演化包括标准C89、C90、C99、C11、C17和C23,C23是C语言标准的一次重大修订,截至2024年3月,最新版本的gcc和 clang实现了C…...

Maven进阶——坐标、依赖、仓库
目录 1.pomxml文件 2. 坐标 2.1 坐标的概念 2.2 坐标的意义 2.3 坐标的含义 2.4 自己项目的坐标 2.5 第三方项目坐标 3. 依赖 3.1 依赖的意义 3.2 依赖的使用 3.3 第三方依赖的查找方法 3.4 依赖范围 3.5 依赖传递和可选依赖 3.5.1 依赖传递 3.5.2 依赖范围对传…...
Android中的内存泄漏及其检测方式
Android中的内存泄漏及其检测方式 一、Android内存泄漏概述 在Android开发中,内存泄漏是一个常见且严重的问题。内存泄漏指的是在应用程序中,由于某些原因,已经不再使用的对象仍然被引用,导致垃圾回收器(Garbage Col…...
【雷电模拟器命令合集操作大全】官方文档整理贴
此贴是官方的帮助整理文档在这里插入代码片 一起来看看几个主要命令,大部分命令读者可以自己试试~ 1、launch 支持2种启动雷电模拟器的方式 –name顾名思义,应该是模拟器的标题栏的名字,本人经过验证果然如此! –index mnq_idx,模…...

redis的配置文件解析
我的后端学习大纲 我的Redis学习大纲 1.1.Redis的配置文件: 1.Redis的配置文件名称是:redis.conf 2.在vim这个配置文件的时候,默认是不显示行号的,可以编辑下面这个文件,末尾加上set nu,就会显示行号: 1.…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...