1 条题解

  • 0
    @ 2025-2-14 21:30:05

    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 ;
    }
    
    • 1

    信息

    ID
    956
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者