题目描述

这一题分析下来，如果知道STL的全排列函数，就可以很容易的做出来；
我们需要求:
现在的排列上加上一个最小数的排列

样例

输入样例：
5
3
1 2 3 4 5
输出样例：
1 2 4 5 3

算法1 通过STL函数进行实现

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10005;
int q[N];
int n,m;

int main(){
    cin >> n >> m ;
    for (int i = 0; i<n; i++)
        cin >> q[i];
    while(m--){
        next_permutation(q,q+n);        
    }
    for(int i = 0; i<n; i++) cout << q[i] << " ";


    return 0;
}

算法二 手写全排列函数

分析参考：
1
2)闫总的代码
分析关键：
1.我们要在现有排列，从后向前遍历这个排列，找出第一个可以让排列变大的位置
2.判断是否能找到更大的序列，当序列单调下降时，如54321，就不能记性排列
3.我们找到ak-1<ak的位置，也就是我们将ak-1变成比他大的最小数，然后将剩余部分从小到大排列
小技巧:
ak-1后面的部分已经从大到小排序好了，因此只需要将其翻转即可。将时间复杂度降低到线性

C++代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int q[N];
int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i <= n; i++)scanf("%d",&q[i]);
    //手动实现全排列 
    while(m--){
        int k = n-1;
        //寻找可以进行排列的位置 ，记录为K值 
        while(q[k-1]>q[k])  k--;
        int t = k--; 
        //确定要交换的第二个值,如果k后面还有 比k前面(也就是q[t])小的数的话叫要先交换那个小的数 
         while(t+1<n &&q[t+1]>q[k]) t++;
         swap(q[t],q[k]);
         reverse(q+k+1,q+n);
    } 
    for(int i = 0; i < n; i++) printf("%d",q[i]);



    return 0;
}