gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2828(线段树)
利用线段树倒推
 1#include <cstdio>
 2
 3const int MAXN = 200100 ;
 4
 5struct NODE
 6{
 7    int start , end ;
 8    int sum ;
 9    NODE *leftc ;
10    NODE *rightc ;
11
12    void Build( const int& s, const int& e ) ;
13    void Insert( int pos ) ;
14} ;
15
16NODE *root , SegTree[MAXN * 2] ;
17int g_Pos , mark , array[MAXN][2] , seq[MAXN] ;
18
19void NODE::Build( const int& s, const int& e )
20{
21    int mid = ( s + e ) >> 1 ;
22    start = s , end = e ;
23    sum = mid - s + 1 ;    //记录此点左边有多少个人
24
25    if ( s == e )
26    {
27        leftc = rightc = NULL ;
28        return ;
29    }
30
31    leftc = &SegTree[g_Pos++] ;
32    rightc = &SegTree[g_Pos++] ;    
33
34    leftc->Build( s , mid ) ;
35    rightc->Build( mid + 1 , e ) ;
36}
37
38void NODE::Insert( int pos )
39{
40    if ( start == end )
41    {
42        mark = start ; //记录最终位置
43        return ;
44    }
45    if ( sum < pos )    //左边人数比指定位置小，则插到右孩子节点 
46    { 
47        pos -= sum ;
48        rightc->Insert( pos ) ;
49    }
50    else if ( sum >= pos )    //否则插到左孩子节点
51    {
52        sum-- ;        //那么左边的人数空位减1
53        leftc->Insert( pos ) ;
54    }
55}
56
57void Init()
58{
59    root = &SegTree[0] ;
60    g_Pos = 1 ;
61}
62
63int main()
64{
65//    freopen("in.txt", "r", stdin) ;
66
67    int n , i ;
68
69    while ( scanf("%d", &n) != EOF )
70    {
71        Init() ;
72
73        for ( i = 0 ; i < n ; ++i )
74        {
75            scanf("%d %d", &array[i][0], &array[i][1]) ;
76        }
77
78        root->Build( 1, n ) ;
79
80        for ( i = n - 1 ; i >= 0 ; --i )
81        {
82            root->Insert( array[i][0] + 1 ) ;
83
84            seq[mark] = array[i][1] ;
85        }
86
87        for ( i = 1 ; i < n ; ++i )
88            printf("%d ", seq[i]) ;
89        printf("%d\n", seq[i]) ;
90    }
91    return 0 ;
92}
posted on 2008-11-18 10:12 巫 阅读(451) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理