企业网站建设与优化/百度指数排行榜哪里看

Lost Cows

题目传送门

• 题意
  FJ有n头牛，编号 1~n ，但是这些牛并没有按照编号排队，但是 FJ 知道每头牛前面有几头编号比这头牛编号小，现在问你每头牛的编号。

• 题解
  从最后一头牛开始，其它牛都已经在队列里，假如这头牛前面有 x 头牛编号比它小，那么这头牛就是编号第 x 小（按编号从小到大排序）的牛的编号加一。知道了这头牛的编号，就可以把这头牛从队列中赶走了，因为有没有它都不会影响到前边的牛。这样，第 n-1 头牛就成了最后一头牛，再重复上面的过程就可以了。
  
  至于解法，可以用暴力解法，每次数 x+1 次，但是复杂度很高，稍有不慎就会超时，但是思路是正确的，只需要降低算法的复杂度就可以了，因为是找第 x+1 头牛的编号，相当于求前缀和，很容易想到的就是树状数组和线段树。相比线段树，树状数组的代码更简洁，因为只涉及区间求和，所以推荐使用树状数组。
  
  还有，树状数组在求区间和的时候使用二分法可以进一步优化。

• AC代码
  
  树状数组

  #include<iostream>
  #include<cstdio>
  using namespace std;
  #define lowbit(x) ((x) & (-x))
  const int MAX = 10000;
  int tree[MAX], pre[MAX], ans[MAX];
  int n;
  void add(int x, int d){while(x<=n){tree[x] += d;x += lowbit(x);}
  }
  int sum(int x){int sum = 0;while(x>0){sum += tree[x];x -= lowbit(x);}return sum;
  }
  int findpos(int x){int l=1, r=n;while(l<r){int mid = (l+r)>>1;if(sum(mid)<x) l = mid+1;else r = mid;}return l;
  }
  int main(){scanf("%d", &n);pre[1] = 0;for(int i=2; i<=n; i++) scanf("%d", &pre[i]);for(int i=1; i<=n; i++) tree[i] = lowbit(i);for(int i=n; i>0; i--){ans[i] = findpos(pre[i]+1);add(ans[i], -1);}for(int i=1; i<=n; i++) printf("%d\n", ans[i]);return 0;
  }
  

  
  线段树

  #include<iostream>
  #include<stdio.h>
  #include<cmath>
  using namespace std;const int MAX = 10000;
  int pre[MAX], tree[4*MAX], ans[MAX];void BuildTree(int n, int last_left){int i;for(i=last_left; i<last_left+n; i++){tree[i] = 1;}while(last_left != 1){for(i=last_left/2; i<last_left; i++){tree[i] = tree[2*i] + tree[2*i+1];}last_left = last_left/2;}
  }int query(int u, int num, int last_left){tree[u]--;if(tree[u]==0 && u>=last_left){return u;}if(tree[u<<1]<num) return query((u<<1)+1, num-tree[u<<1], last_left);else return query(u<<1, num, last_left);
  }int main(){int n, last_left, i;scanf("%d", &n);pre[1] = 0;last_left = 1<<(int(log(n)/log(2))+1);for(i=2; i<=n; i++) scanf("%d", &pre[i]);BuildTree(n, last_left);for(i=n; i>=1; i--) ans[i] = query(1, pre[i]+1, last_left) - last_left + 1;for(i=1; i<=n; i++) printf("%d\n", ans[i]);return 0;
  }