• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 2085-Inversion 求逆序列

POJ解题 第四度 10年前 (2010-08-13) 54次浏览 3个评论 扫描二维码

file

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的最小值)。 代码就容易多了。
更多关于排列和组合的内容,可以参考permutation-generator

#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;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1007.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(3)个小伙伴在吐槽
  1. 谢谢博主,是我理解错了。
    klion262010-08-14 15:35
  2. 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 。 这个问题中运用贪心策略可以逐步确定逆序列,因而可以确定原序列.
    第四度2010-08-14 09:43
  3. 只要知道这样一个事实:一个序列的逆序唯一决定了这个序列。 楼主,对这个不是很理解,望解释。 比如 4 5 3 2 1和5 3 4 2 1的逆序数都是9,或许是我理解有问题?
    klion262010-08-13 23:04