建设网站证书查询,seo短视频网页入口营销策略,手机百度网页版 入口,无锡游戏网站建设公司题意#xff1a;每个奶牛都有一个编号#xff0c;1- N 从第二个牛开始给出前面比她编号小的牛的个数#xff0c;问你求牛的编号序列 解题思路:线段树 二分查找 (多个相同的数二分边界问题需要注意) 解题代码#xff1a; 1 #include stdlib.h2 #include stri…题意每个奶牛都有一个编号1- N 从第二个牛开始给出前面比她编号小的牛的个数问你求牛的编号序列 解题思路:线段树 二分查找 (多个相同的数二分边界问题需要注意) 解题代码 1 #include stdlib.h2 #include string.h3 #include stdio.h4 #define MAXN 80055 struct node6 {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 (pv)/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 else58 {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,n1);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 else93 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
