收藏
关注
定义长度为n的排列为数组 p = [p1, p2, ..., pn] ，这个数组包含n个整数，他们都在1到n之间，并且两两不同。我们说这个排列把1映射到 p1 ，2映射到 p2 ，依此类推。
下面介绍一下排列的循环表示。一个环是一串数字，这一串数字中每一个数字被映射到下一个数字，最后一个数字被映射到第一个数字。排列p的循环表示是由一系列的环构成的。比如排列p = [4, 1, 6, 2, 5, 3]的循环表示是 (142)(36)(5)，因为1映射到4，4映射到2，2映射到1，3和6相互映射，5是自己映射自己。
排列可能会有多个循环表示，所以这儿再定义一个标准的循环表示。第一步，把每一个环中的数字按照降序排列。然后把每一个环按照环中最大的数字升序排列。对于上面的例子， [4, 1, 6, 2, 5, 3]的标准循环表示是(421)(5)(63)。
把环旁边的圆括号拿掉之后我们会得到另外一个排列，比如[4, 1, 6, 2, 5, 3] 会得到 [4, 2, 1, 5, 6, 3]。
一些排列经过上述的变换之后，排列是不变的。现在我们把所有长度为n的满足这样的条件的排列按照字典序排列。请你找出排在第k位的是什么排列。
样例解释：标准循环表示为(1)(32)(4)，拿掉括号之后就是[1 3 2 4]。第一个排列是 [1, 2, 3, 4]，第二个是[1, 2, 4, 3]。
Input
单组测试数据。
第一行包含两个整数 n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ min{10^18,L}，L是符合条件的排列数目。
Output
输出n个以空格分开的数字，代表第k个排列。
Input示例
4 3
Output示例
1 3 2 4
思路
交换之后排列不变的序列只存在两种映射关系
(1) i的映射为i+1 && i+1的映射为 i
(2) i的映射为i
也就是说，只能
交换相邻的两个数
而题目要求字典序排列第k个符合上述要求的序列，想象一下，字典序由小到大也就是
先右后左
的交换，
可以理解为类似冒泡的从后往前冒，区别是会有多个泡泡
代码
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <time.h>
using namespace std;
long long f[55];
int ans[55];
int main()
{
long long n, k;
cin>>n>>k;
f[n] = 1;
f[n+1] = 0;
for(int i=n-1;i>=0;i--)
{
f[i] = f[i+1] + f[i+2];
ans[i] = i+1;
}
for(int i=0;i<n-1 && k;i++)
{
if(k > f[i+1])
{
k -= f[i+1];
swap(ans[i], ans[i+1]);
++i;
}
}
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}