AcWing每日一题--火星人

https://www.acwing.com/problem/content/description/422/

求全排列的字典序的下一个排列 。

可以直接用STL中的next_permutation。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int main(void){
    int n,m;
    vector<int> num;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        num.push_back(t);
    }
    while(m){
        next_permutation(num.begin(),num.end());
        m--;
    }
    for(int i=0;i<num.size();i++){
        cout<<num[i]<<" ";
    }

    return 0;
}

为了更深层次的了解next_permutation的原理，也可以手写一波。

完全逆序的序列是没有下一个全排列的，就得考虑更长的序列。

所以我们首先找到第一个正序的第k个数。

然后从k后面找到最小的大于k的数，因为k后面的数是逆序的，所以直接找就好了。

找到之后将他的位置和k位置互换就好了。再将k后面的序列翻转就好了。

（直接翻转就好是因为k后面是一个逆序的序列）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=10010;
int q[N];
int main(void){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>q[i];
    }
    while(m--){
        int k=n-1;
        while(q[k-1]>q[k])
            k--;
        k--;
        int t=k;
        while(t+1<n&&q[t+1]>q[k]) t++;
        swap(q[k],q[t]);
        reverse(q+k+1,q+n);
    }
    for(int i=0;i<n;i++){
        cout<<q[i]<<" ";
    }
    return 0;
}