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 若余 阅读(1907) 评论(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
谢谢博主,是我理解错了。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

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

统计

常用链接

留言簿

随笔档案(16)

搜索

最新随笔

最新评论

评论排行榜