51Nod 1454 升排列

1454 升排列

题目来源: CodeForces

基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题

收藏

关注

定义长度为n的排列为数组 p = [ p 1 , p 2 , . . . , p n ]
,这个数组包含n个整数,他们都在1到n之间,并且两两不同。我们说这个排列把1映射到 p 1 ,2映射到 p 2 ,依此类推。

下面介绍一下排列的循环表示。一个环是一串数字,这一串数字中每一个数字被映射到下一个数字,最后一个数字被映射到第一个数字。排列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;
}