算法
(贪心,全排列) $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;
}
AC
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
long long n,m,a[10010];
int main(){
cin>>n>>m;
for(int i=0;i[HTML_REMOVED]>a[i];
for(int i=0;i<m;i)
next_permutation(a,a+n);
for(int i=0;i<n-1;i)
cout<<a[i]<<” “;
cout<<a[n-1];
return 0;
}
赞!