wikioi1214-线段覆盖

刺骨的言语ヽ痛彻心扉 2022-07-26 00:30 171阅读 0赞

线段覆盖

题目描述 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

这个跟会场安排实际上是一个类型，按照后面的点从小到大排序（这里注意有可能线段的两个端点是反的），然后逐一判断是否可以留下，注意

1 3

3 5

这种情况是允许的

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    struct node {
    	int b,f;
    }s[100100];
    bool cmp(node x,node y)
    {
    	return x.f<y.f;
    }
    int main()
    {
    	int m,n,i,j,a;
    	scanf("%d",&m);
    		for(i=0;i<m;i++)
    		{
    				scanf("%d%d",&s[i].b,&s[i].f);
    				if(s[i].b>s[i].f)
    				swap(s[i].b,s[i].f);
    		}
    		sort(s,s+m,cmp);
    		int t=0,cot=1;
    		for(i=1;i<m;i++)
    		{
    			if(s[i].b>=s[t].f)
    			{
    				cot++;
    				t=i;
    			}
    		}
    		printf("%d\n",cot);
    	return 0;
     }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 80 阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 75 阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 85 阅读

相关 CodeForces1214C

[CodeForces1214C][] 是个不是很难的题目. 首先考虑如果左右括号数量不匹配那么肯定无论如何都不能通过移动一个括号完成匹配. 否则,我们考虑,将所有

淩亂°似流年/ 2023年06月02日 11:58/ 0 赞/ 157 阅读

相关 CodeForces1214A

[CodeForces1214A][] 说起来你们可能不信,这题硬生生卡了我\\(1h\\),我想了背包,扩欧,二分....等等一坨办法.结果最后还是用了\\(bfs\\)

系统管理员/ 2023年06月02日 11:58/ 0 赞/ 13 阅读

相关【基础练习】【贪心】codevs1214 线段覆盖题解

题目：已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现

偏执的太偏执、/ 2022年08月07日 09:41/ 0 赞/ 195 阅读

相关【基础练习】【贪心】codevs1214 线段覆盖题解

文章被盗还是很严重，加版权信息转载请注明出处 \[[ametake][]版权所有\][http://blog.csdn.net/ametake][ametake]欢迎来看看

我就是我/ 2022年08月01日 15:53/ 0 赞/ 212 阅读

相关 wikioi3027-线段覆盖2

线段覆盖2 题目描述 Description 数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条

痛定思痛。/ 2022年07月26日 00:30/ 0 赞/ 145 阅读

相关 wikioi1214-线段覆盖

线段覆盖题目描述 Description 给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a\_I和b\_I确定，I=1,2,……N.这些坐标都是区间（－9

刺骨的言语ヽ痛彻心扉/ 2022年07月26日 00:30/ 0 赞/ 172 阅读

相关线段树(区间覆盖+区间加法)

include<iostream> include<cstdio> include<cctype> include<cmath> include<cstring> in

不念不忘少年蓝@/ 2021年11月22日 08:54/ 0 赞/ 357 阅读