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

            poj 2085 Inversion 求逆序列


            http://acm.pku.edu.cn/JudgeOnline/problem?id=2085
             

            給定整數N,和一個序列的逆序數M,求以1,2...N為元素,逆序為M,且按字典序最小的那個序列。

            只要知道這樣一個事實:一個序列的逆序唯一決定了這個序列。

            例如:序列1,4,3,2的逆序為1--0,2--2,3--1,4--0,可以用一個四維坐標來表示(0,2,1,0),第i維的數是 i 在原序列中的逆序數,取值范圍是0,1...4-i。

            為解決這個問題,以N=4,逆序數M=5為例。

            1 2 3 4
            最大逆序 3 2 1 0

            對這個問題可以采取貪心策略。
            首先,如果所求序列以1為首,則1的逆序為0,可以從上表看出此時序列的逆序數最多為2+1=3<5,不滿足。考慮以2為首,序列的逆序最多為3+1<5,不滿足。
            考慮以3為首,可見當1的逆序為3,2的逆序為2,4的逆序為0時滿足要求,這時1,2,4均為最大逆序,因而只能排列為4,2,1,加上首數,所求序列為3,4,2,1。

            若M=3,采取同樣的貪心策略,可求得結果為1,4,3,2。

            依此思路,可以得到所求序列關于N,M的關系式,具體如下:
            1,2,3,...N-P,  N-((p-1)*p/2-M),  N  ,  N-1...N-P+1.(P是滿足(P-1)*P/2>=M的最小值)。
            代碼就容易多了。
            關于更多排列的內容可參考:/Files/sdz/s.doc
            #include <stdio.h>
            int main(int argc, char *argv[])
            {
                
            int n,m;
                
            int p,temp,i;
                
            while(scanf("%d%d",&n,&m) && n>0)
                
            {
                    p
            =1;
                    
            while((p*(p-1))/2<m)p++;
                    temp
            =(p*(p-1))/2;
                    
            for(i=1;i<=n-p;i++)
                        printf(
            "%d ",i);
                    printf(
            "%d ",n-temp+m);
                    
            for(i=n;i>=n-p+1;i--)
                    
            {
                        
            if(i!=n-temp+m)
                            printf(
            "%d ",i);
                    }

                    printf(
            "\n");
                }

                
            return 0;
            }



            posted on 2010-08-13 16:13 若余 閱讀(1945) 評論(3)  編輯 收藏 引用

            評論

            # re: poj 2085 Inversion 求逆序列[未登錄] 2010-08-13 23:04 Klion

            只要知道這樣一個事實:一個序列的逆序唯一決定了這個序列。
            樓主,對這個不是很理解,望解釋。
            比如
            4 5 3 2 1和5 3 4 2 1的逆序數都是9,或許是我理解有問題?  回復  更多評論   

            # re: poj 2085 Inversion 求逆序列 2010-08-14 09:43 sdz

            4 5 3 2 1各個數的逆序是1--4,2--3,3--2,4--0,5--0,可以用(4,3,2,0,0)表示這個序列。

            同理,可以用(4,3,1,1,0)表示5 3 4 2 1。
            (4,3,2,0,0)和(4,3,1,1,0)當然是不同的。

            精確描述如下:
            令b1, b2,…, bn為滿足
            0<=b1 <=n-1, 0<=b2 <=n-2, …, 0<=bn-1 <=1, bn =0
            的整數序列,那么存在集合{1,2,…,n}的唯一一個排列,使它的逆序列為b1, b2,…, bn 。


            這個問題中運用貪心策略可以逐步確定逆序列,因而可以確定原序列.  回復  更多評論   

            # re: poj 2085 Inversion 求逆序列[未登錄] 2010-08-14 15:35 Klion

            @sdz
            謝謝博主,是我理解錯了。  回復  更多評論   

            導航

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統計

            常用鏈接

            留言簿

            隨筆檔案(16)

            搜索

            最新隨筆

            最新評論

            評論排行榜

            亚洲狠狠婷婷综合久久蜜芽| 久久中文字幕人妻丝袜| 亚洲香蕉网久久综合影视| 色婷婷久久综合中文久久蜜桃av | 久久99精品久久久久久久久久| 亚洲av日韩精品久久久久久a | 9191精品国产免费久久| 日本加勒比久久精品| 欧美日韩中文字幕久久久不卡| 99久久这里只精品国产免费| 久久99精品久久久久子伦| 久久综合狠狠综合久久97色| 精品久久久久久久无码| 久久www免费人成精品香蕉| 日韩人妻无码精品久久久不卡| 久久99国产精一区二区三区| 一本久道久久综合狠狠爱| 国产日产久久高清欧美一区| 思思久久99热只有频精品66| 久久精品国产亚洲一区二区| 久久久久久综合网天天| 国产一区二区三区久久| 国产精品青草久久久久福利99 | 久久久精品日本一区二区三区 | 69久久夜色精品国产69| 久久久噜噜噜久久中文字幕色伊伊 | 中文字幕亚洲综合久久菠萝蜜 | 无码国内精品久久综合88| 日韩一区二区久久久久久| 国产亚洲欧美成人久久片| 久久综合狠狠综合久久综合88 | 久久精品中文騷妇女内射| 青青久久精品国产免费看| 久久久久久a亚洲欧洲aⅴ| 日韩精品久久久久久久电影蜜臀| 久久天天日天天操综合伊人av| 亚洲国产精品热久久| 青青青青久久精品国产h| 99久久免费国产精品热| 99久久人妻无码精品系列蜜桃| 亚洲精品无码久久久久|