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

            我希望你是我獨家記憶

            一段永遠封存的記憶,隨風而去
            posts - 263, comments - 31, trackbacks - 0, articles - 3
               :: 首頁 :: 新隨筆 ::  :: 聚合  :: 管理

            PKU——2442——(堆的題目)

            Posted on 2008-08-28 15:38 Hero 閱讀(585) 評論(1)  編輯 收藏 引用 所屬分類: 代碼如詩--ACM
            //PKU 2442 Accepted 260K 438MS C++ 2837B 

            //兩個隊列--每次只處理兩行

            //這個題目讓我對"堆"有了新的認識--雙向映射

            #include 
            <stdio.h>
            #include 
            <stdlib.h>
            #include 
            <string.h>

            const int INF = 100000000 ;
            const int size = 2010 ;
            int data1[size] ;
            int point[size] ;//data1[]的每個元素的指針
            int data2[size] ;
            int data3[size] ;//保存data1[]和data2[]相加后的最小inn個元素

            struct QUE
            {
                
            int len ;
                
            int toheap ;
            };
            struct QUE que[size] ;
            //暫存隊列--求出data1[]+data2[]和最小的前n個元素--data3-->data1
            int cque ;
            int heap[size] ;//指向data3[]
            int cheap ;

            int innum ; int ct ;
            int inn, inm ;

            int cmp( const void *a, const void *b )
            {
                
            return *(int *)a - *(int *)b ;
            }

            void input()
            {
                scanf( 
            "%d %d"&inm, &inn ) ;
                
            forint i=1; i<=inn; i++ )
                {
                    scanf( 
            "%d"&data1[i] ) ; point[i] = 1 ; 
                }
                qsort( data1
            +1, inn, sizeof(data1[1]), cmp ) ;

                data1[inn
            +1= INF ;
            }


            void swap( int &a,int &b )
            {
                
            int t = a ; a = b ; b = t ;
            }

            void moveup( struct QUE *dist, int n )
            {
            //將新加入的點向上移動來維持堆,n表示要向上移動的點的坐標

                
            //    while( n&&arry[n]>arry[(n-1)/2] )
                while( n&&dist[heap[n]].len<dist[heap[(n-1)/2]].len )
                {
                    swap( dist[heap[n]].toheap,dist[heap[(n
            -1)/2]].toheap ) ;
                    swap( heap[n],heap[(n
            -1)/2] ) ;
                    n 
            = ( n-1 ) / 2 ;
                }
            }


            void movedown( struct QUE *dist, int n )
            {
            //堆頂改變后,將其向下移動維持堆.n表示堆中元素總數目

                
            int i = 0 ;
                
            while( i+i+1 < n )
                {
                    
            //if( i+i+2<n&&arry[i+i+2]>arry[i+i+1]&&arry[i+i+2]>arry[i] )
                    if( i+i+2<n&&dist[heap[i+i+2]].len<dist[heap[i+i+1]].len&&dist[heap[i+i+2]].len<dist[heap[i]].len )
                    {
                        swap( dist[heap[i
            +i+2]].toheap, dist[heap[i]].toheap ) ;
                        swap( heap[i
            +i+2],heap[i] ) ;
                        i 
            = i+i+2 ;
                    }
                    
            //else if( arry[i+i+1] > arry[i] ) 
                    else if( dist[heap[i+i+1]].len < dist[heap[i]].len )
                    {
                        swap( dist[heap[i
            +i+1]].toheap, dist[heap[i]].toheap ) ;
                        swap( heap[i
            +i+1],heap[i] ) ;
                        i 
            = i+i+1 ;
                    }
                    
            else    break ;
                }
            }

            void process()
            {
                
            forint i=2; i<=inm; i++ )
                {
                    
            forint j=1; j<=inn; j++ )    
                    {
                        scanf( 
            "%d"&data2[j] ) ; 
                    }
            //下一行數據輸入--求兩行和最小的前n個元素
                    qsort( data2+1, inn, sizeof(data2[1]), cmp ) ;

                    cheap 
            = -1 ; data2[inn+1= INF ;//為了避免point[]指針越界
                    forint k=1; k<=inn; k++ )
                    {
                        que[k].len 
            = data1[k] + data2[1] ; point[k] = 1 ;
                        heap[
            ++cheap] = k ; que[k].toheap = cheap ;//先heap再toheap
                    }
                    
            int temp ;
                    
            forint k=1; k<=inn; k++ )
                    {
                        data3[k] 
            = que[heap[0]].len ; //彈出堆頂的元素
                        point[heap[0]]++ ; //printf( "point[%d]==%d\n", heap[0], point[heap[0]] ) ;
                        temp = data1[heap[0]]+data2[point[heap[0]]] ;
                        que[heap[
            0]].len = temp ;//更新que[]隊列的值
                        movedown( que, cheap+1 ) ;
                    }
            //找出和最小的inn個元素

                    
            //memcpy( data1, data3, inn+1 ) ;
                    forint k=1; k<=inn+1; k++ ) data1[k] = data3[k] ;
                }
            }

            void output() 
            {
                
            forint i=1; i<inn; i++ ) printf( "%d ", data1[i] ) ;

                printf( 
            "%d\n", data1[inn] ) ;
            }

            int main()
            {
                
            while( scanf( "%d"&innum ) != EOF )
                {
                    
            forint ct=1; ct<=innum; ct++ )
                    {
                        input() ;

                        process() ;

                        output() ;
                    }
                }

                
            return 0 ;
            }

            Feedback

            # re: PKU——2442——(堆的題目)  回復  更多評論   

            2011-03-15 21:33 by acmer
            謝謝,我用了你的方法過了這道題目!
            可以加你QQ嗎?
            我的QQ是339379406
            久久精品亚洲日本波多野结衣| 国产精品久久自在自线观看| 久久99精品国产99久久6| 久久成人国产精品一区二区| 99久久人人爽亚洲精品美女| 久久国产精品国语对白| 中文精品99久久国产| 久久人人妻人人爽人人爽| 国产精品福利一区二区久久| 99久久精品九九亚洲精品| 久久精品国产亚洲AV忘忧草18| 久久亚洲欧美国产精品| 品成人欧美大片久久国产欧美...| 模特私拍国产精品久久| …久久精品99久久香蕉国产| 人妻丰满?V无码久久不卡| 999久久久无码国产精品| 亚洲精品成人久久久| 91精品国产91久久久久久| 婷婷久久久亚洲欧洲日产国码AV | 久久免费视频6| 91精品国产91久久综合| 久久精品国产99久久久古代| 久久国产精品一区| 青青青国产精品国产精品久久久久 | 久久人人爽人人爽人人片AV麻豆| 国产精品久久久久久久久鸭| 伊人久久久AV老熟妇色| 亚洲国产成人久久综合野外| 国产三级精品久久| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 精品无码久久久久久午夜| 国内精品久久久久影院薰衣草| 一本久久免费视频| 青春久久| 囯产极品美女高潮无套久久久| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 少妇人妻88久久中文字幕| 亚洲精品无码久久久久久| 性色欲网站人妻丰满中文久久不卡| 国产成人精品综合久久久久|