最多能打多少场比赛呢
凌乱的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仓库来存储您的代码呢?…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...