• <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++博客 ::
首頁(yè) ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評(píng)論
				::
				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 ;    //記錄此點(diǎn)左邊有多少個(gè)人
            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 )    //左邊人數(shù)比指定位置小，則插到右孩子節(jié)點(diǎn) 
            46    { 
            47        pos -= sum ;
            48        rightc->Insert( pos ) ;
            49    }
            50    else if ( sum >= pos )    //否則插到左孩子節(jié)點(diǎn)
            51    {
            52        sum-- ;        //那么左邊的人數(shù)空位減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 巫 閱讀(475) 評(píng)論(0)  編輯 收藏 引用  所屬分類: 數(shù)據(jù)結(jié)構(gòu) 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



品成人欧美大片久久国产欧美|
亚洲精品国产字幕久久不卡|
久久97精品久久久久久久不卡|
精品久久久久久中文字幕人妻最新|
成人久久精品一区二区三区|
国产成人久久精品二区三区|
久久精品国产精品亚洲人人
|
人妻精品久久无码区|
人妻久久久一区二区三区|
久久99国产精一区二区三区|
久久久久久av无码免费看大片|
国产精品久久久久蜜芽|
久久国产热精品波多野结衣AV|
99久久国产热无码精品免费久久久久|
亚洲国产精品综合久久网络|
潮喷大喷水系列无码久久精品|
国产亚州精品女人久久久久久|
亚洲综合伊人久久综合|
久久99精品久久久久久不卡|
久久丫精品国产亚洲av不卡|
久久久久久久久久久免费精品|
久久综合精品国产二区无码|
日批日出水久久亚洲精品tv|
亚洲伊人久久大香线蕉苏妲己
|
久久国产欧美日韩精品|
亚洲国产日韩欧美综合久久|
国产精品va久久久久久久|
久久精品中文无码资源站|
久久91精品国产91|
久久久久人妻精品一区三寸蜜桃|
AV狠狠色丁香婷婷综合久久|
中文字幕久久久久人妻|
久久这里都是精品|
午夜精品久久久久久久无码|
久久久久国产一区二区三区|
国产一区二区三精品久久久无广告|
久久婷婷五月综合国产尤物app|
中文字幕无码免费久久|
一本色综合久久|
亚洲人成无码网站久久99热国产
|
看全色黄大色大片免费久久久
|