• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		利用線段樹倒推
            

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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



伊人久久综合成人网|
日韩一区二区三区视频久久|
欧美亚洲国产精品久久久久|
久久久久人妻精品一区三寸蜜桃|
国产精品99久久久久久猫咪|
亚洲国产小视频精品久久久三级|
青青草原精品99久久精品66
|
亚洲国产二区三区久久|
嫩草影院久久国产精品|
欧美一区二区久久精品|
国产成人无码久久久精品一|
久久久久18|
日韩人妻无码一区二区三区久久
|
国产精品成人99久久久久91gav
|
午夜不卡888久久|
青青草原综合久久大伊人|
99久久国产综合精品网成人影院|
久久人人爽人人精品视频
|
久久精品中文字幕有码|
亚洲va中文字幕无码久久不卡|
国产精品99久久久久久猫咪
|
无码任你躁久久久久久|
久久91精品国产91久久小草|
精品久久久噜噜噜久久久|
久久免费99精品国产自在现线|
久久99国产精品尤物|
日本五月天婷久久网站|
久久久久久国产精品免费免费|
avtt天堂网久久精品|
色综合久久中文字幕无码|
久久久久国色AV免费看图片|
久久免费精品一区二区|
WWW婷婷AV久久久影片|
久久夜色精品国产噜噜麻豆|
一本色道久久88精品综合|
久久亚洲精品国产亚洲老地址|
久久免费香蕉视频|
热久久国产欧美一区二区精品|
久久精品国产精品亚洲|
久久这里只有精品视频99|
久久伊人精品青青草原日本|