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

ZesteYdaZ · 2025-03-02 19:59:22 · 题解

分析

可以发现手指数目为 N 的火星人的手指排列顺序是 N 的一个排列，其表示的数是该排列在 N 的全排列中的字典序排名。

那么问题就转化为求 N 的全排列中字典序排名比当前大 M 的那个。

STL 中提供了函数 next_permutation，可以在 O(N) 的时间复杂度内求出给定序列的下一个字典序排列。

那么对火星人手指的排列顺序进行 M 次 next_permutation 即可。

时间复杂度 O(NM)，可以通过本题。

Code

#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;
}