最多能打多少场比赛呢
凌乱的yyy / 线段覆盖
题目背景
快 noip 了,yyy 很紧张!
题目描述
现在各大 oj 上有 n n n 个比赛,每个比赛的开始、结束的时间点是知道的。
yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。
所以,他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 2 2 2 个及以上的比赛。
输入格式
第一行是一个整数 n n n ,接下来 n n n 行每行是 2 2 2 个整数 a i , b i a_{i},b_{i} ai,bi ( a i < b i a_{i}<b_{i} ai<bi ),表示比赛开始、结束的时间。
输出格式
一个整数最多参加的比赛数目。
样例 #1
样例输入 #1
3
0 2
2 4
1 3
样例输出 #1
2
提示
对于 20 % 20\% 20% 的数据, n ≤ 10 n \le 10 n≤10。
对于 50 % 50\% 50% 的数据, n ≤ 1 0 3 n \le 10^3 n≤103。
对于 70 % 70\% 70% 的数据, n ≤ 1 0 5 n \le 10^{5} n≤105。
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 6 1\le n \le 10^{6} 1≤n≤106 , 0 ≤ a i < b i ≤ 1 0 6 0 \le a_{i} < b_{i} \le 10^6 0≤ai<bi≤106。
思路
要求最多能打多少场比赛,那么早结束的比赛就要先打,所以要按比赛结束时间来排序。设定一个变量en来储存上一次比赛结束时间,如果这一次比赛开始时间大于等于上一次比赛结束时间,那么这场比赛就可以打,接着更新en为这次比赛结束时间,方便下一个比较。这里我想分享一下我讨论的一个问题:当区间包含的时候,比如2 3、2 4、3 4,因为原先按比赛结束时间排好了序,所以2 3会打,然后因为2 4的比赛开始时间小于2 3比赛结束时间,所以2 4不会打,接着 3 4会打。也就是说,区间重合时,会筛选出区间内的比赛。因为最外层的那场比赛开始时间小,结束时间大,会被筛掉的。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct Tim
{int s,e;
}t[N];
bool cmp(Tim a,Tim b)
{return a.e<b.e;//按照比赛结束时间从小到大排序
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>t[i].s>>t[i].e;}sort(t,t+n,cmp);int en=0;long long cnt=0;for(int i=0;i<n;i++){if(t[i].s>=en)//大于上次比赛结束时间,区间不重合{en=t[i].e;//更新比赛结束时间cnt++;}else{continue;}}cout<<cnt;return 0;
}
相关文章:
最多能打多少场比赛呢
凌乱的yyy / 线段覆盖 题目背景 快 noip 了,yyy 很紧张! 题目描述 现在各大 oj 上有 n n n 个比赛,每个比赛的开始、结束的时间点是知道的。 yyy 认为,参加越多的比赛,noip 就能考的越好(假的&#x…...

鸿蒙Hi3861学习二-程序烧录与日志输出
一、准备事项 开发板:BearPi-Hm Nano windows工具:HiBurn.exe https://pan.baidu.com/s/18OQD1_BvjNKD_J2e2iX3qg?pwdadrs 提取码:adrs windows工具:MobaXterm和RaiDrive 把ubuntu文件夹映射到windows本地。可以参考如下链接&am…...
typescript Awaited<Type>教程用法
typescript Awaited教程用法 文章目录 typescript Awaited<Type>教程用法 ts4.5发布了Awaited,但是很多人不明白Awaited的用法。 首先看一下官方的说明:这种类型旨在模拟函数await中的操作async,或 s.then()上的方法——特别是它们递归…...
AES硬件运算单元
功能描述 AES单元主要功能如下: 支持解密密钥扩展 支持128bit/192bit/256bit的密钥长度支持ECBCBCCTRM支持DMA进行自动数据传输 支持GF(2^128)域下的乘法,支持GMAC 工作模式 AES有4种工作模式,通过配置MODE1:0]寄存器设置。 模式1:用存储在AES KEYRx寄存…...
mulesoft MCIA 破釜沉舟备考 2023.04.28.26 (易错题)
mulesoft MCIA 破釜沉舟备考 2023.04.28.26 (易错题) 1. According to MuleSoft, what is a major distinguishing characteristic of an application network in relation to the integration of systems, data, and devices?2. An integration team follows MuleSoft’s r…...

k210单片机定时器的应用
定时器应该是一个单片机的标准配置,所以k210也是有的,拥有3个定时器,具体的使用方法我们往下看: 分步介绍: 首先是相关模块的使用 构造函数: machine.Timer(id,channel,modeTimer.MODE_ONE_SHOT,period100…...
linux0.12-7-1
[272页] 第7章 初始化程序 1、main.c主要内核初始化工作。 2、如果能完全理解这里调用的所有程序,那么看完这张内容后应该对Linux内核有了大致的了解。 3、 有一定的C语言知识 4、 需要GNU gcc手册在身边作为参考,因为在内核代码很多地方使用gcc的扩展…...
设置 文本框 自动填充背景颜色 为白色
关于autofill伪类的 兼容性: 在现代浏览器中,包括Chrome、Safari、Firefox等,都支持:autofill伪类,但在使用时必须加上浏览器前缀-webkit-,即:-webkit-autofill。 在旧版的浏览器中,可能不支持:autofill伪…...

Bitmap引起的OOM问题
作者:向阳逐梦 1.什么是OOM?为什么会引起OOM? 答:Out Of Memory(内存溢出),我们都知道Android系统会为每个APP分配一个独立的工作空间,或者说分配一个单独的Dalvik虚拟机,这样每个APP都可以独立…...

【JavaEE初阶】认识线程(Thread)
目录 🌾 前言 🌾 了解线程 🌈1.1 线程是什么? 🌈1.2 一些基本问题 🌾2、创建线程的方式 🌈 2.1 继承Thread类 🌈 2.2 实现Runnable接口并重写run()方法 🌈 注意…...

自动化运维工具一Ansible Roles实战
目录 一、Ansible Roles概述 1.1.roles官方的目录结构 1.2.Ansible Roles依赖关系 二、Ansible Roles案例实战 2.1.Ansible Roles NFS服务 2.2 Roles Memcached 2.3 Roles-rsync服务 一、Ansible Roles概述 之前介绍了 Playbook 的使用方法,对于批量任务的部…...
json 中有递归parentId节点转 c#实体类时如何处理
如果您有一个具有递归parentId节点的JSON数据,并且您需要将其转换为C#实体类,则可以使用以下方法: 创建一个类来表示JSON对象的节点,包括它的属性和子节点。 public class Node {public int Id { get; set; }public string Name …...

给大家介绍几个手机冷门但好用的小技巧
技巧一:拍照识别植物 手机的拍照识别植物功能是指在使用手机相机时,可以通过对植物进行拍照,并通过植物识别技术,获取植物的相关信息和资料。其主要优点如下: 方便实用:使用拍照识别植物功能,…...

2.3 定点乘法运算
学习目标: 如果我要学习定点乘法运算,我会按照以下步骤进行学习: 确定学习目标:明确学习定点乘法运算的目的和重点,以便有针对性地进行学习。 掌握基础知识:首先需要了解定点数和定点乘法的基础知识&…...

C++每日一练:打家劫室(详解动态规划法)
文章目录 前言一、题目二、分析三、代码总结 前言 这题目出得很有意思哈,打劫也是很有技术含量滴!不会点算法打劫这么粗暴的工作都干不好。 提示:以下是本篇文章正文内容,下面案例可供参考 一、题目 题目名称: 打家…...
Wireshark使用
Capture Filters 语法 <Protocol name><Direction><Hosts><Value><Logical operations><Expressions> e.g 1.tcp src port 443 只抓取来源端口是443的tcp数据 2.not arp 不获取arp数据 3.port 80 获取端口是80的数据,不指…...

这才是 SpringBoot 统一登录鉴权、异常处理、数据格式 的正确姿势
本篇将要学习 Spring Boot 统一功能处理模块,这也是 AOP 的实战环节 用户登录权限的校验实现接口 HandlerInterceptor WebMvcConfigurer 异常处理使用注解 RestControllerAdvice ExceptionHandler 数据格式返回使用注解 ControllerAdvice 并且实现接口 Response…...

Java面试题总结 | Java面试题总结6-MYSQL模块(持续更新)
Mysql 文章目录 Mysql关系型数据库和非关系型数据库的区别什么是ORM?-**mybatis**如何评估一个索引创建的是否合理?Count函数执行效果上:执行效率上:count(主键)和count(列名) 数据库的三大范式Mysql中char和varchar的区别数据库设计或者功能…...
Linux命令集(Linux文件管理命令--mv指令篇)
Linux命令集(Linux文件管理命令--mv指令篇) Linux文件管理命令集(mv指令篇)2. mv(move)1. 文件移动2. 递归移动目录3. 文件目录重命名4. 强制移动5. 备份覆盖的目标文件6. 试探性移动7. 显示移动进度8. 补集操作9. 修改文件的权限…...
不一样的 Git 之间 | GitLab vs GitHub vs Gitee vs GitCode
Git仓库对比:GitLab vs GitHub vs Gitee vs GitCode 在软件开发中,版本控制是必不可少的工具之一。Git作为目前最为流行的版本控制系统,也逐渐成为了开发者们的标配。但是,如何选择一个合适的Git仓库来存储您的代码呢?…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...