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

I- yh的线段(2023河南萌新联赛第(四)场:河南大学)

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

yh喜欢好线段,好线段即两条线段相交且不与其他线段重合的线段。

两条线段[l1,r1]和[l2,r2]相交(如果存在至少一个x,使得l1≤x≤r1和l2≤x≤r2,则认为两个线段相交)。

yh在数轴上有几条线段,他可以把在数轴上相交的线段结合,但是对于每个线段只能与其它线段结合一次,且不能与其它线段有重合部分,yh可以舍弃任何数量的线段。

给你nn (2≤n≤1e6)条线段,如果两条线段相交且不与其他线段相交,则由这两条线段组成的线段被称为好线段,线段不能被重复使用,但可以被舍弃任意数量的线段,请你找出好线段个数的最大值。

输入描述:

第一行包含一个正数nn (2≤n≤1e6)——线段的个数。
接下来 nn行各包含两个整数li 和 ri (0≤li≤ri≤10^9,表示n 个线段。

输出描述:

输出好线段个数的最大值。

示例1

输入

复制

5
2 2
2 8
0 10
1 2
5 6

输出

复制

1

示例2

输入

复制

7
2 4
9 12
2 4
7 7
4 8
10 13
6 8

输出

复制

3

说明

对于样例2,我们可以删除[4,8]这一条线段,然后将[2,4]和[2,4]、[6,8]和[7,7]、[9,12]和[10,13]组成三条好线段,可以看出这是最优的情况。

思路:

         将所有线段,按照右端点从小到大进行排序。找到俩俩包含的,如果后面出现想包裹住前面的直接跳过;

 当出现俩俩融合一线段之后,又出现一条直线想包含其中一条直线,那直接跳过


 

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"hear!"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
#define endl "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double,long double> PDD;ll  INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
//   return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 1e6+ 10;
const ll mod1 =998244353;
const ll mod2 =1e9+7;
const ll hash_num = 3e9+9;
ll n,m,ca, k,ans;
ll arr[N],brr[N],crr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;struct node
{ll l, r;
}noda[N];bool cmp(node a,node b)
{if(a.r==b.r){return a.l>b.l;}return a.r<b.r;
}void solve()
{cin >> n;rep(i,1,n){cin >> noda[i].l >> noda[i].r;}sort(noda+1,noda+1+n,cmp);ll ans=0;ll f=-1,r=-1;// cout << endl;// rep(i,1,n)// {//     cout << noda[i].l <<"  "<<noda[i].r<<endl;// }// cout << endl;rep(i,1,n){if(noda[i].l<=f)continue;else if(noda[i].l<=r){ans++;f=noda[i].r;}else{r=noda[i].r;}// cout << f << "  "<<r<<endl;}cout << ans;
}int main()
{IOS;ll _;_=1;//get_eulers();//scanf("%lld",&_);//cin>>_;ca=1;while(_--){solve(); ca++;}    return 0;
}

相关文章:

I- yh的线段(2023河南萌新联赛第(四)场:河南大学)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 yh喜欢好线段&#xff0c;好线段即两条线段相交且不与其他线段重合的线段。 两条线段[l1,r1]和[l2,r2]相交(如果存在至少一个x&#xff0c;使得l1≤x≤r1和l2≤x≤r2&#xff0c;则认为两个线段…...

python与深度学习(十四):CNN和IKUN模型二

目录 1. 说明2. IKUN模型的CNN模型测试2.1 导入相关库2.2 加载模型2.3 设置保存图片的路径2.4 加载图片2.5 图片预处理2.6 对图片进行预测2.7 显示图片 3. 完整代码和显示结果4. 多张图片进行测试的完整代码以及结果 1. 说明 本篇文章是对上篇文章猫狗大战训练的模型进行测试。…...

chrome扩展在popup、background、content之间通信解决传输文件问题

文章目录 背景介绍案例介绍代码示例popup页面&#xff0c;上传文件页面popup页面&#xff0c;js上传代码&#xff0c;file文件转base64background监听消息&#xff0c;base64转file文件&#xff0c;axios上传 附-转base64后直接下载 背景介绍 示例扩展API版本MV2。 以弹…...

Oracle获取创建对象的DDL脚本

Oracle获取创建对象的DDL脚本 Oracle获取创建对象的DDL脚本查看 dbms_metadata.get_ddl()函数的定义 Oracle获取创建对象的DDL脚本 例如&#xff0c;对tzq schema下的表 test2&#xff0c;查看DDL脚本的SQL如下&#xff1a; SELECT SELECT dbms_metadata.get_ddl(upper(table…...

《算法竞赛·快冲300题》每日一题:“01树”

《算法竞赛快冲300题》将于2024年出版&#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码&#xff0c;以中低档题为主&#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 0…...

Mac提示文件:已损坏,无法打开。你应该把它移到废纸篓

文章目录 一、电脑信息二、打开任何来源设置三、更改应用程序拓展属性 一、电脑信息 我的是新版的Venture 13的系统。UI改的比较多。与之前的配置还是有很大的区别的。 打开下载的软件&#xff0c;显示已经损坏&#xff0c;打不开。抛开软件本身的问题外&#xff0c;一般是Ma…...

探索嵌入式系统:从入门到实践

随着科技的飞速发展&#xff0c;嵌入式系统已经成为了我们生活中不可或缺的一部分。从智能手机、智能家居到工业自动化设备&#xff0c;嵌入式系统的应用已经渗透到了各个领域。那么&#xff0c;如何学习嵌入式系统呢&#xff1f;本文将从入门到实践&#xff0c;为你详细解答。…...

网络安全知识点整理(作业2)

目录 一、js函数声明->function 第一种 第二种 第三种 二、this关键字 this使用场合 1.全局环境 2.构造函数 3.对象的方法 避免多层this 三、js的同步与异步 定时器 setTimeout和setInterval 同步与异步的例子 四、宏任务与微任务 分辨宏任务与微任务 一、js…...

idea数据库快速上手-库操作与表结构和数据操作

引言 对数据库的操作无非就是执行SQL语句&#xff0c;要想熟练操作数据库&#xff0c;就要熟练运用SQL语句。 一&#xff0c;数据库操作 展示当前服务器内的数据库 -- 展示服务器内的数据库 show databases; show schemas; 执行结果&#xff1a; 创建数据库&#xff1a; --…...

当“国潮”遇见“双语” 以传承之心种下一颗文化的种子

看&#xff0c;活灵活现的纸片人在“跳舞”。光影的辉映下&#xff0c;两个形神兼备的“齐天大圣”究竟孰真孰假&#xff1f;舞台上&#xff0c;京西皮影非遗传承人王熙和5岁的Mona小朋友正在用双语为大家带来一段“真假美猴王”的好戏。生动的皮影造型和精彩的故事演绎看得台下…...

计划管理与项目管理:有何区别?

简而言之&#xff0c;是的。尽管它们经常互换使用并对全局产生影响&#xff0c;但它们是完全不同的。 在本文中&#xff0c;我们将了解计划和项目管理之间的差异&#xff0c;提供每个示例&#xff0c;并向您展示如何使计划和项目管理工作更有效地实现您的业务目标。 计划管理与…...

个人信息保护合规审计如何做?

8月3日&#xff0c;为指导、规范个人信息保护合规审计活动&#xff0c;根据《中华人民共和国个人信息保护法》等法律法规&#xff0c;国家互联网信息办公室就《个人信息保护合规审计管理办法&#xff08;征求意见稿&#xff09;》&#xff08;简称《办法》&#xff09;及配套的…...

HTTP杂谈之Referer和Origin请求头再探

一 关于Referer和Origin的汇总 1) 知识是凌乱的,各位看官看个热闹即可2) 内容不断更新1、理解有盲区,需要及时纠正2、内容交叉有重复,需要适当删减3、扩展视野3) 以下内容都与Referer和Origin请求头有关联 nginx防盗链 HTTP杂谈之Referrer-Policy响应头 iframe标签referre…...

数学建模-爬虫入门

Python快速入门 简单易懂Python入门 爬虫流程 获取网页内容&#xff1a;HTTP请求解析网页内容&#xff1a;Requst库、HTML结果、Beautiful Soup库储存和分析数据 什么是HTTP请求和响应 如何用Python Requests发送请求 下载pip macos系统下载&#xff1a;pip3 install req…...

HSRM各表

文章目录 表规则接口种类服务与网关路由菜单一、采购申请1、采购申请—查询2、采购申请-操作记录二、采购申请跟踪报表1、采购申请跟踪报表—列表查询三、寻源1、寻源大厅—列表查询2、寻源大厅—询价单明细3、寻源大厅—物料明细4、寻源大厅—供应商列表5、寻源模板—列表查询…...

Ansible自动化运维工具 —— Playbook 剧本

playbooks 本身由以下各部分组成 &#xff08;1&#xff09;Tasks&#xff1a;任务&#xff0c;即通过 task 调用 ansible 的模板将多个操作组织在一个 playbook 中运行 &#xff08;2&#xff09;Variables&#xff1a;变量 &#xff08;3&#xff09;Templates&#xff1a;模…...

第二章:多态

系列文章目录 文章目录 系列文章目录前言多态的概念概念 多态的定义及实现多态的构成条件虚函数虚函数的重写C11 override 和 final重载、覆盖(重写)、隐藏(重定义)的对比 抽象类概念接口继承和实现继承 多态的原理虚函数表多态的原理动态绑定与静态绑定 单继承和多继承关系的虚…...

C++面向对象设计基础

一般类、&、const、模板、友元函数、操作符重载基本用法及实现 complex.h #ifndef COMPLEX_H #define COMPLEX_H #include<ostream> using namespace std;template<typename T> class Complex{public:Complex():re(0),img(0){}// 为什么构造函数不能传引用&a…...

Linux定时运行sh脚本,如果sh文件已经在运行,则忽略本次运行

需求来源 我需要linux的crontab定期每10分钟运行lan.sh脚本。但由于lan.sh运行需要较长时间&#xff0c;有时超过10分钟。这样会导致系统多次运行lan.sh脚本&#xff0c;引发运行堆积&#xff0c;导致一些非必要的错误。 解决方法 解决方法是写一个脚本&#xff0c;如果lan.…...

SpringBoot项目中的web安全防护

最近这个月公司对项目进行了几次安全性扫描&#xff0c;然后扫描出来了一些安全漏洞&#xff0c;所以最近也一直在修复各种安全漏洞&#xff0c;还有就是最近在备考软考高级系统架构设计师&#xff0c;也刚好复习到了网络安全这一个章节&#xff0c;顺便将最近修复的安全漏洞总…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...