排列排序

内存限制: 256 Mb时间限制: 1000 ms

题目描述

如果一个整数序列 a1​,a2​,…,an​ 的每个数字都在 1 到 n 之间，且没有两个数字相等，则称这个序列为全排列。例如1,3,2 以及 4,3,2,1 都是全排列。

我们将所有的全排列排序，定义全排列 a1​,a2​,…,an​ 与 b1​,b2​,…,bm​ 的排序先后关系如下：

• 如果 n<m，则 a 序列更靠前
• 如果 n>m，则 b 序列更靠前
• 如果 n=m，则以字典序规则比较 a 序列与 b 序列，字典序更小的序列更靠前。

根据上述定义，可以得到

• 第 1 个全排列是 1
• 第 2 个全排列是 1 2
• 第 3 个全排列是 2 1
• 第 4 个全排列是 1 2 3

给定 k，请输出第 k 个全排列。

输入格式

• 单个整数：表示 k

输出格式

• 单独一行：表示第 k 个全排列

数据范围

• 30% 的数据 1≤k≤1000
• 60% 的数据 1≤k≤1,000,000
• 100% 的数据 1≤k≤10^15

样例数据

 输入:
5
输出:
1 3 2
说明:

解析：

根据样例找出规律，一个数字的全排列是1，两个数字的全排列是2，三个数字的全排列是6，。。。n个数字的全排列是n的阶乘。

我们可以先算出他是几个数字组成的全排列，然后再用搜索找到他；

详见代码：

#include <bits/stdc++.h>
using namespace std;
long long k;
long long jc[105];
bool b[55];//标志该数是否被使用
int w;//答案是几个数字的全排列
void myprint(long long s,int step){//搜索
    if (step==0) return;//所有数字完成，返回
    long long x=(s-1)/jc[step-1]+1;//首位是第几个数字
    for (int i=1;i<=w;i++){
        if (b[i]==0){//没用过
            x--;
            if (x==0){
                printf("%d ",i);//打印
                b[i]=1;//标记已使用
                break;
            }
        }
    }
    s%=jc[step-1];
    if (s==0) s=jc[step-1];
    myprint(s,step-1);
}
int main() {
    cin>>k;
    jc[0]=1;
    long long sum=0;
    for (int i=1;sum<=k;i++){
        jc[i]=jc[i-1]*i;//求i的阶乘
        sum+=jc[i];//求前i个数字组成的全排列一共多少个
        w=i;//求出w
    }
    for (int i=1;i<w;i++){
        k-=jc[i];//求出答案在w个数字组成的全排列中的序号
    }
    myprint(k,w);//搜索打印
    return 0;
}