ZOJ 2319 Beautiful People-白红宇

ZOJ 2319 Beautiful People

阅读量：6841 次

发布时间：2019-06-26

本文共 998 字，大约阅读时间需要 3 分钟。

LIS。先按S降序升序再按B降序排序（如果B不按降序排序的话就会覆盖掉正解），然后再对B用O(nlog(n))的LIS求解就可以了。用d数组标记每个元素在上升序列中的位置，然后根据d倒着找id就可以了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define FF(i, a, b) for(int i=a; i
                   
                    =b; i--)#define REP(i, n) for(int i=0; i
                    
                      rhs.b); }}p[N];int g[N];int d[N];int main(){ int s, b, t, n, ans; scanf("%d", &t); while(t --) { scanf("%d", &n); for(int i = 0; i < n; i ++) { scanf("%d%d", &s, &b); p[i].s = s, p[i].b = b, p[i].id = i + 1; } sort(p, p + n);ans = 0; for(int i = 1; i <= n; i ++) g[i] = INF; for(int i = 0; i < n; i ++) { int k = lower_bound(g+1, g+n+1, p[i].b) - g; g[k] = p[i].b; d[i] = k; ans = max(ans, k); } printf("%d\n", ans); int pt = -1; for(int i = n - 1; i >= 0; i --) { if(p[i].s != pt && d[i] == ans) { printf("%d", p[i].id); if(ans) putchar(' '); ans --;pt = p[i].s; } if(!ans) break; }puts(""); if(t) puts(""); }}

转载地址：http://ikdul.baihongyu.com/

你可能感兴趣的文章