• <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) 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



国产高潮国产高潮久久久91
|
久久夜色精品国产网站|
无码久久精品国产亚洲Av影片
|
国产精品久久久久久久久软件|
奇米影视7777久久精品人人爽|
日本久久久久亚洲中字幕|
99精品国产在热久久|
久久亚洲高清综合|
久久久免费精品re6|
久久精品国产亚洲Aⅴ香蕉
|
欧美国产成人久久精品|
69国产成人综合久久精品|
久久五月精品中文字幕|
99久久99这里只有免费费精品|
蜜桃麻豆www久久国产精品|
国产精品久久午夜夜伦鲁鲁|
日韩久久无码免费毛片软件|
97久久久久人妻精品专区|
久久久久久精品免费看SSS|
久久99精品久久久久久齐齐|
97精品久久天干天天天按摩|
人妻精品久久久久中文字幕69
|
久久精品国产69国产精品亚洲|
亚洲国产成人久久精品99
|
精品人妻久久久久久888|
欧美大战日韩91综合一区婷婷久久青草|
色婷婷久久综合中文久久蜜桃av|
少妇被又大又粗又爽毛片久久黑人|
久久精品男人影院|
久久精品国产亚洲网站|
国内精品伊人久久久久av一坑
|
国产精品日韩深夜福利久久
|
国产毛片久久久久久国产毛片
|
久久国产精品-久久精品|
久久久无码人妻精品无码|
国内高清久久久久久|
久久精品国产99国产精品导航|
久久只有这精品99|
久久人妻AV中文字幕|
亚洲欧美一级久久精品|
亚洲AV伊人久久青青草原|