题意
已知一个排列,以字典序为顺序,输出其后的第m个排列。
解法探究:
全排列问题:
对于全排列问题,我们知道,用dfs可以很轻松的解出。其复杂度为n^n
此题与全排列
对于这道题,一个最直观的蛮力算法为:在dfs的过程中,遇到所给序列开始计数,输出后面第M个序列。
但是数据范围为N<=1e4, M <= 100; 显然是不可以从1,2,3,4,5…这个序列开始遍历的。而我们注意到,M仅仅为100。所以如果可以从所给序列开始搜索,那么时间复杂度并不会超。
那么怎么才能从所给的序列开始dfs呢?
伪造递归现场
首先我们思考一个问题:递归版本的dfs是如何利用函数调用栈的?
//简化的dfs求全排列代码
void f(int n, int dep){
if(dep == n)
return;
for(int x = 0; x < n; x++)
f(n, dep+1);
}
假设某一时刻,函数调用栈如下所示(从下往上为调用次序):
f: dep = 5, x = 3, n = 10
f: dep = 4, x = 6, n = 10
f: dep = 3, x = 2, n = 10
f: dep = 2, x = 4, n = 10
f: dep = 1, x = 5, n = 10
main()
可以看出,栈里记录的有用信息,仅仅是每一层中x
的值。比如在第一层,栈中的x是5,从dep = 2, x = 4的f函数中返回时,我们就可以继续在x = 6时往下进行递归。
所以我们仅仅需要在函数调用栈中模拟出每个x的值即可。
如何实现?
在第一次往下搜索的时候,可以直接给x赋值为arr[dep]
然后在回溯过程中在按正常的顺序进行dfs。
AC代码如下:
#include <bits/stdc++.h>
using namespace std;
int arr[10005];
int usd[10005];
//int last[10005];
int m;
int dWflag = 1; //是否正在往下
stack<int> ans;
void dfs(int n, int dep){
int x = 0; //这里的初始化为0是必要的
if(dWflag){ //伪造现场
x = arr[dep];
if(dep == n-1){
dWflag = 0;
usd[arr[dep]] = 0;
return;
}
dfs(n, dep+1);
}
if(dep == n){
m--;
return ;
}
usd[x] = 0; //正常的dfs,遍历x后面可用的数字
for(x = x+1; x <=n && m; x++){
if(usd[x])
continue;
usd[x] = 1;
dfs(n, dep+1);
usd[x] = 0;
}
//usd[x] = 0;
if(!m)
ans.push(x-1); //从循环里出来的x都是加了1的
}
int main(void){
int n;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%d", arr+i);
}
for(int i = 1; i <=n; i++)
usd[i] = 1;
dfs(n, 0);
for(int i = 0; i < n; i++){
if(!ans.empty()){
printf("%d ",ans.top());
ans.pop();
}
}
}
谢谢!收获很大
厉害了 我DFS 时间过不去