最多能打多少场比赛呢
凌乱的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仓库来存储您的代码呢?…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...

认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...

rm视觉学习1-自瞄部分
首先先感谢中南大学的开源,提供了很全面的思路,减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接:https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架: 代码框架结构:readme有…...
FTXUI::Dom 模块
DOM 模块定义了分层的 FTXUI::Element 树,可用于构建复杂的终端界面,支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...