codevs 1214线段覆盖
2024-10-21 18:30:00
1214 线段覆盖
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
给定x轴上的N(0<N<100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N.这些坐标都是区间(-999,999)的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序,从给出的线段中去掉尽量少的线段,使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部(即除去端点的部分)。
输入描述 Input Description
输入第一行是一个整数N。接下来有N行,每行有二个空格隔开的整数,表示一条线段的二个端点的坐标。
输出描述 Output Description
输出第一行是一个整数表示最多剩下的线段数。
样例输入 Sample Input
3
6 3
1 3
2 5
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
0<N<100
【题目大意】求最多的互不覆盖的线段的个数。
【思路】贪心 右端点升序排列 选择右端点较小的线段 为剩下的线段留下更多的位置。
【code】
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct E
{
int x,y;
}s[];
int c[],n,last=-,ans;
bool cmp(E a,E b)
{
if(a.x==b.x)return a.y<b.y;
return a.y<b.y;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&s[i].x,&s[i].y);
if(s[i].x>s[i].y)swap(s[i].x,s[i].y);
}
sort(s+,s+n+,cmp);
for(int i=;i<=n;i++)
if(s[i].x>=last)
{
ans++;last=s[i].y;
}
printf("%d\n",ans);
return ;
}
最新文章
- 3-EM的安装和使用
- SharePoint 2013 图文开发系列之创建内容类型
- 解决Type &#39;UnityEngine.Component&#39; does not support slicing
- VSS记住用户名和密码
- Android 在C代码中调用logcat
- 抽象数据类型ADT
- 改变DataGrid某一行和单元格的颜色
- 转:CPU与内存的那些事
- phonegap android3.5.1 Crosswalk
- petshop4.0 具体解释之中的一个(系统架构设计)
- Entity Framework 插入数据 解决主键非自增问题
- html5结合flash实现视频文件在所有主流浏览器兼容播放
- Spring Boot Security 详解
- Codeforces Round #544 (Div. 3)解题报告
- TCP 选项RST
- Linux拉你入门
- shareSdk分享图片
- supervisor详解
- Linux下修改MySQL数据库字符编码为UTF-8解决中文乱码
- JDK的下载及配置