算法

(贪心,全排列) $O(nm)$

这道题目可以直接用next_permutation函数来做。

这里我们考虑一下next_permutation函数的原理，然后手动实现一遍。

对于给定的某个排列，我们想求出比它大的最小的排列。
可以从后往前遍历这个排列，找到第一个可以让排列的字典序变大的位置。

只有当序列单调下降时，它才不存在更大的排列，因此我们要找的位置就是第一次出现 $a_{k-1} < a_k$ 的位置。

那么此时将 $a_{k-1}$ 变成比它大的最小数，然后将剩余部分从小到大排序，得到的排列就是比原排列大的最小排列了。

这里有个小优化：

• 由于 $a_{k-1}$ 后面的部分已经从大到小排好序，因此只需将其翻转，就可以得到从小到大排序的结果了，不需要使用 sort函数，时间效率可以降到线性。

时间复杂度

一共求 $m$ 次next_permutation，每次需要 $o(n)$ 的时间，因此总时间复杂度是 $O(nm)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ ) scanf("%d", &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[t], q[k]);
        reverse(q + k + 1, q + n);
    }

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}