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