题目连接:http://poj.org/problem?id=2182
题意描述:有n头牛,编号从1到n,现告诉n-1头牛每头牛前面编号比它小的牛的数量,求一个惟一的排列。
题意分析:一道线段树的最基础的应用。

代码如下:

#include<stdio.h>
#include<string.h>
#include<stdio.h>

#define MAX 8005

struct nodes{

   int l,r;
   int len;
}tree[ MAX*4 ];

int cow[MAX];
int num[MAX];

//建立线段树,静态链表存储
void BuildTree( int root, int left, int right ){
   tree[root].l = left;
   tree[root].r = right;
   tree[root].len = right – left + 1;
   if( left == right )
       return ;
   int mid = ( left + right ) / 2;
   BuildTree( root*2, left,mid );
   BuildTree( root*2+1, mid+1, right );
}

//查找线段树
int Query( int root, int m ){
   tree[root].len –;
   //如果左右孩子一样,返回
   if( tree[root].l == tree[root].r )
       return tree[root].l;
       //如果m<len,说明该数位于左孩子
   else if( m <= tree[ root*2 ].len )
       return Query( root*2, m );
   else        //如果m>len,说明该数位于右孩子
       return Query( root*2+1, m-tree[root*2].len );
}

int main(){
   int n;
   int i;
   while( scanf( “%d”, &n ) != EOF ){
       for( i=1; i<n; i++ )
           scanf( “%d”, &cow[i] );
       BuildTree( 1,1,n );
       for( i=n-1; i>=1; i– )
           num[i] = Query( 1, cow[i]+1 );
       num[0] = Query( 1,0+1 );
       for( i=0; i<n; i++ )
           printf( “%d\n”, num[i] );
   }
   return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation