当前位置: 首页 > news >正文

最多能打多少场比赛呢

凌乱的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 n10

对于 50 % 50\% 50% 的数据, n ≤ 1 0 3 n \le 10^3 n103

对于 70 % 70\% 70% 的数据, n ≤ 1 0 5 n \le 10^{5} n105

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 6 1\le n \le 10^{6} 1n106 0 ≤ a i < b i ≤ 1 0 6 0 \le a_{i} < b_{i} \le 10^6 0ai<bi106

思路

要求最多能打多少场比赛,那么早结束的比赛就要先打,所以要按比赛结束时间来排序。设定一个变量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 了&#xff0c;yyy 很紧张&#xff01; 题目描述 现在各大 oj 上有 n n n 个比赛&#xff0c;每个比赛的开始、结束的时间点是知道的。 yyy 认为&#xff0c;参加越多的比赛&#xff0c;noip 就能考的越好&#xff08;假的&#x…...

鸿蒙Hi3861学习二-程序烧录与日志输出

一、准备事项 开发板&#xff1a;BearPi-Hm Nano windows工具&#xff1a;HiBurn.exe https://pan.baidu.com/s/18OQD1_BvjNKD_J2e2iX3qg?pwdadrs 提取码&#xff1a;adrs windows工具&#xff1a;MobaXterm和RaiDrive 把ubuntu文件夹映射到windows本地。可以参考如下链接&am…...

typescript Awaited<Type>教程用法

typescript Awaited教程用法 文章目录 typescript Awaited<Type>教程用法 ts4.5发布了Awaited&#xff0c;但是很多人不明白Awaited的用法。 首先看一下官方的说明&#xff1a;这种类型旨在模拟函数await中的操作async&#xff0c;或 s.then()上的方法——特别是它们递归…...

AES硬件运算单元

功能描述 AES单元主要功能如下: 支持解密密钥扩展 支持128bit/192bit/256bit的密钥长度支持ECBCBCCTRM支持DMA进行自动数据传输 支持GF(2^128)域下的乘法&#xff0c;支持GMAC 工作模式 AES有4种工作模式&#xff0c;通过配置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单片机定时器的应用

定时器应该是一个单片机的标准配置&#xff0c;所以k210也是有的&#xff0c;拥有3个定时器&#xff0c;具体的使用方法我们往下看&#xff1a; 分步介绍&#xff1a; 首先是相关模块的使用 构造函数&#xff1a; machine.Timer(id,channel,modeTimer.MODE_ONE_SHOT,period100…...

linux0.12-7-1

[272页] 第7章 初始化程序 1、main.c主要内核初始化工作。 2、如果能完全理解这里调用的所有程序&#xff0c;那么看完这张内容后应该对Linux内核有了大致的了解。 3、 有一定的C语言知识 4、 需要GNU gcc手册在身边作为参考&#xff0c;因为在内核代码很多地方使用gcc的扩展…...

设置 文本框 自动填充背景颜色 为白色

关于autofill伪类的 兼容性&#xff1a; 在现代浏览器中&#xff0c;包括Chrome、Safari、Firefox等&#xff0c;都支持:autofill伪类&#xff0c;但在使用时必须加上浏览器前缀-webkit-&#xff0c;即:-webkit-autofill。 在旧版的浏览器中&#xff0c;可能不支持:autofill伪…...

Bitmap引起的OOM问题

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

【JavaEE初阶】认识线程(Thread)

目录 &#x1f33e; 前言 &#x1f33e; 了解线程 &#x1f308;1.1 线程是什么&#xff1f; &#x1f308;1.2 一些基本问题 &#x1f33e;2、创建线程的方式 &#x1f308; 2.1 继承Thread类 &#x1f308; 2.2 实现Runnable接口并重写run()方法 &#x1f308; 注意…...

自动化运维工具一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 的使用方法&#xff0c;对于批量任务的部…...

json 中有递归parentId节点转 c#实体类时如何处理

如果您有一个具有递归parentId节点的JSON数据&#xff0c;并且您需要将其转换为C#实体类&#xff0c;则可以使用以下方法&#xff1a; 创建一个类来表示JSON对象的节点&#xff0c;包括它的属性和子节点。 public class Node {public int Id { get; set; }public string Name …...

给大家介绍几个手机冷门但好用的小技巧

技巧一&#xff1a;拍照识别植物 手机的拍照识别植物功能是指在使用手机相机时&#xff0c;可以通过对植物进行拍照&#xff0c;并通过植物识别技术&#xff0c;获取植物的相关信息和资料。其主要优点如下&#xff1a; 方便实用&#xff1a;使用拍照识别植物功能&#xff0c;…...

2.3 定点乘法运算

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

C++每日一练:打家劫室(详解动态规划法)

文章目录 前言一、题目二、分析三、代码总结 前言 这题目出得很有意思哈&#xff0c;打劫也是很有技术含量滴&#xff01;不会点算法打劫这么粗暴的工作都干不好。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、题目 题目名称&#xff1a; 打家…...

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的数据&#xff0c;不指…...

这才是 SpringBoot 统一登录鉴权、异常处理、数据格式 的正确姿势

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

Java面试题总结 | Java面试题总结6-MYSQL模块(持续更新)

Mysql 文章目录 Mysql关系型数据库和非关系型数据库的区别什么是ORM?-**mybatis**如何评估一个索引创建的是否合理&#xff1f;Count函数执行效果上&#xff1a;执行效率上&#xff1a;count(主键)和count(列名) 数据库的三大范式Mysql中char和varchar的区别数据库设计或者功能…...

Linux命令集(Linux文件管理命令--mv指令篇)

Linux命令集&#xff08;Linux文件管理命令--mv指令篇&#xff09; Linux文件管理命令集&#xff08;mv指令篇&#xff09;2. mv(move)1. 文件移动2. 递归移动目录3. 文件目录重命名4. 强制移动5. 备份覆盖的目标文件6. 试探性移动7. 显示移动进度8. 补集操作9. 修改文件的权限…...

不一样的 Git 之间 | GitLab vs GitHub vs Gitee vs GitCode

Git仓库对比&#xff1a;GitLab vs GitHub vs Gitee vs GitCode 在软件开发中&#xff0c;版本控制是必不可少的工具之一。Git作为目前最为流行的版本控制系统&#xff0c;也逐渐成为了开发者们的标配。但是&#xff0c;如何选择一个合适的Git仓库来存储您的代码呢&#xff1f;…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...