色综合久久久久久久久五月,久久亚洲高清综合,一本大道久久a久久精品综合

Pku 2828(線段樹)

利用線段樹倒推

#include <cstdio>
2

const int MAXN = 200100 ;
4

struct NODE
6

{
7

int start , end ;
8

int sum ;
9

NODE *leftc ;
10

NODE *rightc ;
11

void Build( const int& s, const int& e ) ;
13

void Insert( int pos ) ;
14

} ;
15

NODE *root , SegTree[MAXN * 2] ;
17

int g_Pos , mark , array[MAXN][2] , seq[MAXN] ;
18

void 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

if ( s == e )
26

{
27

leftc = rightc = NULL ;
28

return ;
29

}
30

leftc = &SegTree[g_Pos++] ;
32

rightc = &SegTree[g_Pos++] ;
33

leftc->Build( s , mid ) ;
35

rightc->Build( mid + 1 , e ) ;
36

}
37

void 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

void Init()
58

{
59

root = &SegTree[0] ;
60

g_Pos = 1 ;
61

}
62

int main()
64

{
65

// freopen("in.txt", "r", stdin) ;
66

int n , i ;
68

while ( scanf("%d", &n) != EOF )
70

{
71

Init() ;
72

for ( i = 0 ; i < n ; ++i )
74

{
75

scanf("%d %d", &array[i][0], &array[i][1]) ;
76

}
77

root->Build( 1, n ) ;
79

for ( i = n - 1 ; i >= 0 ; --i )
81

{
82

root->Insert( array[i][0] + 1 ) ;
83

seq[mark] = array[i][1] ;
85

}
86

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 巫閱讀(470) 評論(0) 編輯收藏引用所屬分類: 數據結構

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 7th GDCPC Problem H(DFS序 + 線段樹) POJ 3368 (RMQ) POJ 3368 Frequent values (線段樹) POJ 2060--Taxi Cab Scheme(最小路徑覆蓋) Atomic Nucleus Investigation (線段樹 n = 100000) POJ 2481(樹狀數組) POJ 2481 Cows(線段樹) POJ 3667 Hotel(模擬) Pku 2828(線段樹) Pku 2777(線段樹)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論