• <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 - 33,  comments - 33,  trackbacks - 0
            題意:
            給出兩種操作:ADD(x),將x添加到有序列表中;GET()返回全局迭代器所指的值,其中迭代器在GET操作后會(huì)自添加1
            題解:
            剛開始直接手打鏈表模擬,結(jié)果超時(shí)。這時(shí)應(yīng)使用另外一種方法:使用大頂堆和小頂堆。
            其中,對于序列S[1..n],及表示迭代器位置的index,大頂堆維護(hù)排序后的S[1..index-1],小頂堆維護(hù)
            排序后的S[index..n],例如S[1..n] = 1,2,3,4,5,6,7,index = 4,則大頂堆為{1,2,3},小頂堆為{4,5,6,7}
            為什么要這樣維護(hù)呢?因?yàn)楫?dāng)小堆最小的元素都大于大堆最大的元素時(shí),那么序列中排第n個(gè)就是小堆最小的數(shù)了。
            我們假設(shè)第k趟GET()后,有以下情景(GET后k自動(dòng)加1):
            大頂堆:S[1..k],堆頂元素為S[k],小頂堆:S[k+1,n],堆頂元素為S[k+1],然后每當(dāng)添加一個(gè)元素newE時(shí),先添加到大頂堆中,這時(shí)如果出現(xiàn)大頂堆數(shù)大于小頂堆的數(shù)時(shí),理應(yīng)交換。
            代碼:
            #include <queue>
            #include 
            <stdio.h>
            using namespace std;

            int m,n;
            int sequence[30005];

            struct cmp1
            {
                
            bool operator()(const int a,const int b)
                
            {
                    
            return a>b;
                }

            }
            ;
            struct cmp2
            {
                
            bool operator()(const int a,const int b)
                
            {
                    
            return a<b;
                }

            }
            ;

            void Test()
            {
                priority_queue
            <int,vector<int>,cmp1>q1;//小堆
                priority_queue<int,vector<int>,cmp2>q2;//大堆

                
            for (int i = 0; i < m; ++i)
                
            {
                    scanf(
            "%d",&sequence[i]);
                }

                
            int op;
                
            int k = 0;
                
            for (int i = 0; i < n; ++i)
                
            {
                    scanf(
            "%d",&op);
                    
            while(k < op)
                    
            {
                        q1.push(sequence[k]);
                        
            if (!q2.empty() && q1.top() < q2.top())
                        
            {
                            
            int t1 = q1.top();
                            q1.pop();
                            
            int t2 = q2.top();
                            q2.pop();
                            q1.push(t2);
                            q2.push(t1);
                        }

                        
            ++k;
                    }

                    printf(
            "%d\n",q1.top());
                    q2.push(q1.top());
                    q1.pop();
                }


            }


            int main()
            {
                
            while(scanf("%d %d",&m,&n) != EOF)
                
            {
                    Test();
                }

                
            return 0;
            }

            posted on 2011-06-02 15:34 bennycen 閱讀(1699) 評論(0)  編輯 收藏 引用 所屬分類: 算法題解
            久久精品国产亚洲AV麻豆网站| 久久精品人人做人人妻人人玩| 性欧美大战久久久久久久久 | 国产精品日韩深夜福利久久 | 国产精品99久久久久久宅男| 97久久精品人人做人人爽| 久久久精品国产亚洲成人满18免费网站| 久久99热狠狠色精品一区| 72种姿势欧美久久久久大黄蕉| 国产精品久久久久久久久久免费| 精品久久久久久无码中文野结衣| 久久精品免费一区二区| 免费无码国产欧美久久18| 狠狠色丁香婷婷久久综合不卡| 国产精品美女久久久网AV| 亚洲va久久久噜噜噜久久| 久久精品无码av| 国产成人久久精品区一区二区| 亚洲精品无码久久毛片| 成人午夜精品久久久久久久小说 | 久久无码人妻一区二区三区 | 色狠狠久久综合网| 九九热久久免费视频| 日本欧美久久久久免费播放网| 久久久久国产精品嫩草影院| AV无码久久久久不卡网站下载| 国产精品久久久久久久久软件| 人人狠狠综合久久亚洲婷婷| 91亚洲国产成人久久精品网址| 色偷偷久久一区二区三区| 久久久精品人妻一区二区三区蜜桃| 久久亚洲精品视频| 777久久精品一区二区三区无码 | 国产精品伊人久久伊人电影 | 一本色道久久综合狠狠躁篇| 久久福利片| 久久精品亚洲乱码伦伦中文 | 久久高清一级毛片| 久久青青草原精品国产不卡| 久久国产精品无| 久久亚洲精品国产精品婷婷|