P1791 线段覆盖
2024-10-21 05:06:27
题目描述
已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi(Ai<>Bi,i=1..N)定义。端点坐标在(-999,999)内,坐标为整数。有些线段可能相交。编程实现删除最少数目的线段,使得余下的任意两条线段不相交。
输入输出格式
输入格式:
第一行为一整数N。接下来有N行,每行包含两个整数 (Ai 和 Bi), 用空格隔开。
输出格式:
整数p,即删除后余下的线段数。
输入输出样例
输入样例#1:
3
6 3
1 3
2 5
输出样例#1:
2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x;
int y;
}a[];
int comp(const node & a , const node & b)
{
return a.y<b.y;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
if(a[i].x>a[i].y)
swap(a[i].x,a[i].y);
} sort(a+,a+n+,comp);
int last=-;
int ans=;
for(int i=;i<=n;i++)
{
if(a[i].x>=last)
{
ans++;
last=a[i].y;
}
}
printf("%d",ans);
return ;
}
最新文章
- Wakez计算与压缩的思考
- Python语言十分钟快速入门
- Replication的犄角旮旯(一)--变更订阅端表名的应用场景
- 设计模式之美:Builder(生成器)
- Linux下shell颜色配置
- 使用新的AppleID更新Xcode
- [开发笔记]-jQuery获取checkbox选中项等操作及注意事项
- 第十六篇、MBprogressHUD的使用和获取当前的控制器
- 华为 2015 机试 输出:数字后面的连续出现的(2个或多个)相同字符(数字或者字符),删去一个,非数字后面的不要删除,例如,对应输出为:33aabb55pin。
- PHP读取CSV大文件导入数据库的示例
- error2
- 认识 var、let、const
- 学号 20175329 2018-2019-3《Java程序设计》第六周学习总结
- Flask 模板系统
- JAVA课堂测试之一位数组可视化
- JavaScript 对象(下)
- 设置dataGridView单元格颜色、字体、ToolTip、字体颜色
- arithmetic-02
- sql特殊语法
- BZOJ2154/BZOJ2693/Luogu1829 Crash的数字表格/JZPFAR 莫比乌斯反演
热门文章
- WinThruster中文版破解方法(注册表无伤清理工具)
- hihoCoder2月29日(字符串模拟)
- asio 中strand的作用
- weex 安装过程中遇到的坑
- py-day1简单使用方法及语法使用详解
- HDOJ-2058
- 微信小程序开发之三元运算符代替wx.if/wx.else
- 您的Microsof Internet Explorer浏览器包含新版本的内置Adobe Flash Player。
- [ACM] hdu 1285 确定比赛名次 (拓扑排序)
- 2019ICPC西安邀请赛 - B. Product - 数论