AcWing 420. 火星人
原题链接
中等
作者:
wyf
,
2021-01-28 11:28:49
,
所有人可见
,
阅读 456
全排列问题:刚开始考虑为求出整个n的全排列,但是通过观察数据范围可以得出,dfs为指数级别复杂度,若求出全部则一定会超时,那么我们可以选择从当前数列开始,往后做m次从而得出答案,首先寻找可以进行全排列的位置,其次确定要交换的两个值,如果k后面还有比k前面小的数,就先交换小的数
#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;
while(q[k-1]>q[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-1; i++) printf("%d ",q[i]);
printf("%d\n",q[n-1]);
return 0;
}