若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1712: 排列的字典序问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,056

题目描述

n个元素{1,2,……, n }有n!个不同的排列。将这n!个排列按字典序排列,并编号为0,1,…,n!-1。每个排列的编号为其字典序值。例如,当n=3时,6 个不同排列的字典序值如下:

给定n以及n个元素{1,2,……, n }的一个排列,计算出这个排列的字典序值,以及按字典序排列的下一个排列。

输入

输入数据的第1行是元素个数n(n≤20)。接下来的1行是n个元素 {1,2,……, n }的一个排列。

输出

输出数据的第1行是字典序值,第2行是按字典序排列的下一个排列。

样例输入

8
2 6 4 5 8 1 7 3

样例输出

8227
2 6 4 5 8 3 1 7

参考代码

#include<stdio.h>
#include<stdlib.h>
void SWAP(int * a, int * b) 
{
    long long t;
    t = *a;
    *a = *b;
    *b = t;
}
int main() 
{
    int n,i,k,j,t,order[100];
    int lis,f[100],mid,h;
    f[0]=1;
    for (i=1;i<=22;i++)
            f[i]=f[i-1]*i;
    while(scanf("%d",&n)!=EOF) 
    {
        for (i=0;i<n;i++)
                    scanf("%d",&order[i]);
        if(n==1)    printf("0n1n");
        else if(n>=2)
        {
            lis=0;
            for(i=0,k=n-1;i<n-1;i++,k--)
            {
                t=0;
                for(j=0;j<i;j++)
                    if(order[j]<order[i])    t++;
                lis+=(order[i]-1-t)*f[k];
            }
            printf("%dn",lis);
            for(i = n-2; i >= 0; i--)
            {
                if(order[i] < order[i+1])
                {
                    j = i;
                    for(k = n-1; k > j; k--)
                    {
                        if(order[k] > order[j])
                        {
                            mid = j+(n-j)/2;
                            SWAP(&order[j], &order[k]);
                            for(j++, h = 1; j <= mid; j++, h++)
                                SWAP(&order[j], &order[n-h]);
                        }
                    }
                    break;
                }
            }
            for(i=0; i < n-1; i++)
                printf("%d ",order[i]);
            printf("%d",order[i]);
        }
    }
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist