解法一:找规律
时间复杂度:$O(m \times n)$
该题是需要发现某些性质,即如何寻找一个排列的下一个排列。
1 2 3 5 4
一眼可以看出下一个排列为 1 2 4 3 5
为什么呢?
首先我们从右向左看,找到第一个满足 $q[k] < q[k + 1]$ 的位置,因为这个位置就是恰好将字典序变大且变大的最小的位置(越靠右,字典序改变的幅度越小),此时 $k$ 的右边一定单调递减,再找到一个恰好大于 $q[k]$ 的最小数 $q[t]$ 进行交换,右边也一定单调递减,因为此时的 $q[t] > q[k] > q[t + 1]$,所以只需将 $k + 1$ 后面的数反转即可实现 $k$ 后面的数单调递增。
用一幅图表示即为:
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m;
int q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> q[i];
while (m--) { // 相当于自己实现 next_permutation 函数
int k = n - 2;
while (q[k] > q[k + 1]) --k;
int t = k + 1;
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;
}
解法二:next_permutation 函数
时间复杂度:$O(m \times n)$
直接调用 next_permutation 函数返回下一个序列即可。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int n, m;
int q[N];
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] << ' ';
cout << endl;
return 0;
}