(构造)

每次从后向前找到第一个非逆序的位置，即s[i-1]<s[i]，那么就让s[i-1]等于i~n-1中比s[i-1]大的最小数s[k]，交换s[i-1],s[k]，然后将i~n-1升序排序。

时间复杂度

$O(nm)$

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<int> v;
void nex(){
    for(int i=n-1;i>=0;--i){
        if(v[i]>v[i-1]){
            int k=i; 
            for(int j=n-1;j>=i;--j)
                if(v[j]>v[i-1]&&v[j]<v[k]) k=j;
            swap(v[k],v[i-1]);
            sort(v.begin()+i,v.end());
            return ;
        }
    }
}
int main(){
    cin>>n>>m;
    string s="";
    for(int i=0,x;i<n;++i){
        cin>>x;
        v.push_back(x);
    }
    while(m--) nex();
    for(auto t : v) cout<<t<<" ";
    return 0;
}