HDU 1027 Ignatius and the Princess II 排列生成

解题报告：1-n这n个数，有n!中不同的排列，将这n!个数列按照字典序排序，输出第m个数列。

第一次TLE了，没注意到题目上的n和m的范围，n的范围是小于1000的，然后m的范围是小于10000的，很明显，如果暴力枚举的话，时间复杂度就是O(n*m)，为10^7，所以可以通过。这题其实就是一个排列生成的题，排列生成有多种方法，这题的关键是当找到答案的时候，要及时退出暴力过程，要不然肯定TLE。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int num,n,m,visit[1005],flag;
 7 
 8 void dfs(int* A,int deep)
 9 {
10     if(flag) return ;
11     if(deep - 1 == n)
12     {
13         num++;
14         if(num == m)
15         {
16             for(int i = 1;i<=n;++i)
17             printf(i==1? "%d":" %d",A[i]);
18             flag = 1;
19             return ;
20         }
21     }
22     else
23     {
24         for(int i = 1;i<=n;++i)
25         if(!visit[i])
26         {
27             A[deep] = i;
28             visit[i] = 1;
29             dfs(A,deep+1);
30             visit[i] = 0;
31         }
32     }
33 }
34 
35 int main() 
36 {
37     int A[1005];
38     while(scanf("%d%d",&n,&m)!=EOF)
39     {
40         num = flag = 0;
41         memset(visit,0,sizeof(visit));
42         dfs(A,1);
43         printf("
");
44     }
45     return 0;
46 }
47

View Code