[数据结构与算法]洛谷P1088 [NOIP2004 普及组] 火星人

传送门：https://www.luogu.com.cn/problem/P1088

一个全排列问题，可以把洛谷P1706写了再来写。

P1706：?https://www.luogu.com.cn/problem/P1706

? ? ? 看到题目的我的第一反应就是DFS，模拟全排列的过程，然后找到火星人给的排列顺序，然后接着往下找M个全排列就能找到答案。但是题目的数据开到10000，很明显这样的做法会超时。所以不能去慢慢找火星人给的顺序，应该是要在极短的时间内就锁定该排列在整个搜索过程中的位置，然后接着往下找M次。思路有了，怎么用代码实现呢？其他步骤都比较好些，关键是怎么快速找到火星人给的顺序？?

? ? ? 由此引出该解法的核心代码跳转? ? if (!amount) i = ans[step];? 读者可以先阅读代码段直到该行再翻上来看解释。

? ? ? 这行核心代码实现的是跳转到这次搜索的起始位置。为什么这样写呢？先举一个1到5的全排列为例子，在用DFS实现1到5全排列的时候，第一个全排列是1 2 3 4 5 。由于在我们的搜索中有循环的存在，我们才得以枚举所有情况。那么如果把一个DFS的递归工作栈展开，就是一个多重循环，那么这个多重循环的i的值都不一样，都在特定的位置上，搜索到哪个数字就等于哪个数字。由于要快速找到火星人给的顺序，就必须确定该顺序的多重循环的每一个i的值。因此i=ans[step];ans存放的是火星人给的排列，由此可以确定每一个i。

#include<iostream>
#define MAX 10005
using namespace std;
int ans[MAX]; bool visit[MAX];
//ans数组用来存放排列顺序，visit标记
int M = 0, N = 0, amount = 0;bool flag = false;
//amount用于存储目前在哪个全排列
//flag是用来判别是否已经找到答案
void DFS(int step) {
	if (flag)return;
	//如果已经找到答案就一直return直到DFS函数结束
	if (step > N) {//边界
		amount++;//一个全排列就加1
		if (amount == M+1) {
			//这边的判定条件要注意是M+1
			//因为火星人最开始给出的排序也加进amount里
			flag = true;//找到了
			for (int i = 1; i <= N; i++)
				printf("%d ", ans[i]);
			//输出答案并return
			return;
		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (!amount) i = ans[step];
		//核心代码，懂了后问题迎刃而解
		//跳转到该次DFS的相应位置
		//代码段外有详细解释
		if (!visit[i]) {
			visit[i] = true;
			ans[step] = i;
			DFS(step + 1);
			visit[i] = false;
		}
		//典型的全排列模板
		//如果不会可以先把 P1706的全排列问题研究明白再做这题
	}
}
int main(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		scanf("%d", &ans[i]);
	DFS(1);//从1开始搜索
	return 0;//完结撒花
}