游客 注册 | 登录
中文 | En

3046 - 卡片

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

每个卡片的开头和结尾都有标记，把每张卡片看成数轴上的一条线段，开头和结尾的标记A,B为数轴上的两个点。每张卡片的颜色都不同。将卡片按照标记贴到数轴上，请问贴完卡片以后的数轴上一共有多少种不同的颜色。

题目输入

第1行：一个整数N，表示卡片的数量。

第2行至第N＋1行：第i+1行给出了第i张卡片的头尾两个标记Ai,Bi，贴卡片的顺序与输入文件中出现的先后顺序一致。

题目输出

一个整数，表示能在数轴上看到的不同的颜色的数目。

输入/输出样例

输入格式

4
0 5
3 8
5 6
4 7

输出格式

3

C++解答

#include <cstdio>

#define  maxn  20001

int n , i , j , k , ans ;
int l[maxn] = {0} , r[maxn] = {0} ;
bool v[maxn] = {0} ;

void up(int ll , int rr , int t ) {
	//不知所云的浮水法 
	if (v[i]) return ;
	while (t<=n && (l[t]>=rr || r[t]<=ll)) t ++ ;
	if (t > n) {
		ans ++ ;
		v[i] = true ;
	}
	if (ll<l[t] && rr>l[t]) up(ll,l[t],t+1) ;
	if (ll<r[t] && rr>r[t]) up(r[t],rr,t+1) ;
}

int main() {
	scanf("%d", &n ) ;
	for (i = 1 ; i <= n ; i ++ ) scanf("%d%d", &l[i] , &r[i] ) ;
	for (i = n-1 ; i > 0 ; i -- ) up(l[i],r[i],i+1) ;
	ans ++ ;
	printf("%d\n", ans ) ;
	return 0 ;
}
请先登陆