线段树/树状数组 POJ 2182 Lost Cows-白红宇

线段树/树状数组 POJ 2182 Lost Cows

阅读量：6240 次

发布时间：2019-06-22

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

题意：n头牛，1~n的id给它们乱序编号，已知每头牛前面有多少头牛的编号是比它小的，求原来乱序的编号

分析：从后往前考虑，最后一头牛a[i] = 0，那么它的编号为第a[i] + 1编号：为1，倒数第二头牛的编号为除去最后一头牛的编号后的第a[i-1] + 1编号：为3，其他的类推，所以可以维护之前已经选掉的编号，求第k大的数字，sum[rt] 表示该区间已经被选掉的点的个数。另外树状数组也可以做，只不过用二分优化查找第k大的位置。

收获：逆向思维，求动态第K大

代码(线段树)：

/************************************************* Author        :Running_Time* Created Time  :2015/9/9 星期三 17:01:08* File Name     :P.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 8e3 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;struct ST { int sum[N<<2]; void build(int l, int r, int rt) { sum[rt] = 0; if (l == r) return ; int mid = (l + r) >> 1; build (lson); build (rson); } int query(int p, int l, int r, int rt) { sum[rt]++; if (l == r) return l; int mid = (l + r) >> 1; int tmp = mid - l + 1 - sum[rt<<1]; if (tmp >= p) return query (p, lson); else { return query (p - tmp, rson); } }}st;int a[N], ans[N];int main(void) { int n; while (scanf ("%d", &n) == 1) { a[1] = 0; for (int i=2; i<=n; ++i) { scanf ("%d", &a[i]); } st.build (1, n, 1); for (int i=n; i>=1; --i) { ans[i] = st.query (a[i] + 1, 1, n, 1); } for (int i=1; i<=n; ++i) { printf ("%d\n", ans[i]); } } return 0;}

代码(树状数组)：

/************************************************* Author        :Running_Time* Created Time  :2015/9/9 星期三 18:19:28* File Name     :P_BIT.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 8e3 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int n;struct BIT { int c[N]; void init(void) { memset (c, 0, sizeof (c)); } void updata(int i, int x) { while (i <= n) { c[i] += x; i += i & (-i); } } int query(int i) { int ret = 0; while (i) { ret += c[i]; i -= i & (-i); } return ret; } int bsearch(int l, int r, int k) { while (l <= r) { int mid = (l + r) >> 1; if (mid - query (mid) >= k) r = mid - 1; else l = mid + 1; } return l; }}bit;int a[N], ans[N];int main(void) { while (scanf ("%d", &n) == 1) { a[1] = 0; for (int i=2; i<=n; ++i) scanf ("%d", &a[i]); bit.init (); for (int i=n; i>=1; --i) { ans[i] = bit.bsearch (1, n, a[i] + 1); bit.updata (ans[i], 1); } for (int i=1; i<=n; ++i) { printf ("%d\n", ans[i]); } } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4795660.html

你可能感兴趣的文章