3046 - 卡片
每个卡片的开头和结尾都有标记，把每张卡片看成数轴上的一条线段，开头和结尾的标记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 ; }