思维+差分,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.…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...