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

Dark_Blue_Sky · 2025-03-01 09:54:26 · 题解

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

题目简述

火星人有编号为 1,2,3,\cdots,n 的手指，这些手指可以组成 1 \sim N 个大小互不相同的数，形成一个序列。这些序列按字典序从小到大排序。你需要做的是：求出比给出序列大的所有序列中第 m 小的序列。

分析

不难发现，火星人的手指编号不重复，那么每一个序列都是一个排列。而序列字典序从小到大的顺序就是 C++ 中 next_permutation 中的排列顺序。因此，我们只需要用 next_permutation 函数重复 m 次，就可以求出比给出序列大的所有序列中第 m 小的序列了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];//input
    for(int i=1;i<=m;i++)next_permutation(a+1,a+n+1);//求出比给出序列大的所有序列中第 m 小的序列
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";//output
    return 0;
}