題意：每個奶牛都有一個編號，1- N 從第二個牛開始給出前面比她編號小的牛的個數，問你求牛的編號序列

解題思路:線段樹+ 二分查找　(多個相同的數二分邊界問題需要注意)　

解題代碼：

1 #include <stdlib.h> 2 #include <string.h> 3 #include <stdio.h> 4 #define MAXN 8005 5 struct node 6 { 7 int left , right,mid ; 8 int num; 9 }tree[MAXN*4]; 10 int L(int c) 11 { 12 return 2 * c; 13 } 14 int R(int c) 15 { 16 return 2 * c + 1; 17 } 18 void up(int c ) 19 { 20 tree[c].num = tree[L(c)].num + tree[R(c)].num; 21 } 22 void build(int c ,int p , int v) 23 { 24 tree[c].left = p ; 25 tree[c].right = v ; 26 tree[c].mid = (p+v)/2; 27 tree[c].num = 1; 28 if(p == v ) 29 { 30 return; 31 } 32 build(L(c),p,tree[c].mid); 33 build(R(c),tree[c].mid + 1, v ); 34 up(c); 35 } 36 void update(int c , int p) 37 { 38 if(tree[c].left == p && tree[c].right == p ) 39 { 40 tree[c].num = 0 ; 41 return ; 42 } 43 if(p <= tree[c].mid) update(L(c),p); 44 else update(R(c),p); 45 up(c); 46 } 47 int tsum = 0 ; 48 void getsum (int c, int p , int v ) 49 { 50 if(p <= tree[c].left && v >= tree[c].right) 51 { 52 tsum += tree[c].num; 53 return ; 54 } 55 if(v <= tree[c].mid) getsum (L(c),p,v); 56 else if(p > tree[c].mid) getsum(R(c),p, v); 57 else 58 { 59 getsum(L(c),p,tree[c].mid); 60 getsum(R(c),tree[c].mid + 1, v ); 61 } 62 } 63 int a[MAXN]; 64 int b[MAXN]; 65 int main() 66 { 67 int n ; 68 while(scanf("%d",&n) != EOF) 69 { 70 memset(a,0,sizeof(a)); 71 memset(b,0,sizeof(b)); 72 for(int i = 2; i <= n;i ++) 73 scanf("%d",&a[i]); 74 b[n] = a[n] + 1; 75 build(1,1,n+1); 76 update(1,b[n]); 77 for(int i = n- 1; i >=1 ;i --) 78 { 79 int low = 1 , high = n; 80 int ans ; 81 while(low <= high) 82 { 83 tsum = 0 ; 84 85 int mid = (low + high)/2; 86 getsum(1,1,mid); 87 if(tsum >= a[i]+1) 88 { 89 ans = mid ; 90 high = mid - 1; 91 } 92 else 93 low = mid +1; 94 } 95 // printf("%d\n",ans); 96 b[i] = ans ; 97 tsum = 0 ; 98 getsum(1,1,ans); 99 // printf("%d\n",tsum); 100 update(1,b[i]); 101 } 102 for(int i = 1;i <= n; i ++) 103 printf("%d\n",b[i]); 104 } 105 return 0 ; 106 } View Code

?

轉載于:https://www.cnblogs.com/zyue/p/3224570.html

總結

以上是生活随笔為你收集整理的poj 2182 Lost Cows 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。