题解：P1088 [NOIP 2004 普及组] 火星人

分析

可以发现手指数目为

N

的火星人的手指排列顺序是

N

的一个排列，其表示的数是该排列在

N

的全排列中的字典序排名。

那么问题就转化为求

N

的全排列中字典序排名比当前大

M

的那个。

STL 中提供了函数 next_permutation，可以在

O(N)

的时间复杂度内求出给定序列的下一个字典序排列。

那么对火星人手指的排列顺序进行

M

次 next_permutation 即可。

时间复杂度

O(NM)

，可以通过本题。

Code

CPP

#include<bits/stdc++.h>
#define i64 long long

using namespace std;

constexpr int N=10005;
int n,m,a[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];

    for(int _=1;_<=m;++_)next_permutation(a+1,a+n+1);

    for(int i=1;i<=n;++i)cout<<a[i]<<' ';
    return 0;
}

题解：P1088 [NOIP 2004 普及组] 火星人

文章操作

分析

Code

相关推荐

评论

题解：P1088 [NOIP 2004 普及组] 火星人