链接地址：
OpenJudge：http://bailian.openjudge.cn/practice/1833
Poj: http://poj.org/problem?id=1833
题目：
排列
Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 15320 Accepted: 6202 Description
题目描述：
大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。
任务描述：
给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。Input
第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。Output
对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。Sample Input
3 3 1 2 3 1 3 1 3 2 1 10 2 1 2 3 4 5 6 7 8 9 10Sample Output
3 1 2 1 2 3 1 2 3 4 5 6 7 9 8 10Source
思路：
（1）思路按照《程序设计引导及在线实践》的思路，有一点不同里面提到要重新排序，其实主要做一个逆序即可
（2）里面输入输出必须使用C语言的，不然会TLE
（3）可使用STL的next_permutation,也可参照对应源码的思路，参考资料在此：http://leonard1853.iteye.com/blog/1450085
代码：
1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4 5 int main() 6 { 7 int m; 8 cin>>m; 9 int i,j,x; 10 int temp; 11 while(m--) 12 { 13 int n,k; 14 scanf("%d %d",&n,&k); 15 int *arr = new int[n]; 16 for(i = 0; i < n; i++) scanf("%d",&arr[i]); 17 while(k--) 18 { 19 for(i = n-1; i > 0; i--) 20 { 21 if(arr[i-1] < arr[i]) 22 { 23 int idx = i; 24 for(j = i+1;j < n;j++) 25 { 26 if(arr[j] > arr[i-1] && arr[j] < arr[idx]) 27 { 28 idx = j; 29 } 30 } 31 temp = arr[idx]; 32 arr[idx] = arr[i-1]; 33 arr[i-1] = temp; 34 /*for(j = n-1; j >= i; j--) 35 { 36 for(x = i; x < j; x++) 37 { 38 if(arr[x] > arr[x+1]) 39 { 40 temp = arr[x]; 41 arr[x] = arr[x+1]; 42 arr[x+1] = temp; 43 } 44 } 45 }*/ 46 for(j = i; j <= (n-1+i)/2; j++) 47 { 48 temp = arr[j]; 49 arr[j] = arr[n-1-(j-i)]; 50 arr[n-1-(j-i)] = temp; 51 } 52 break; 53 } 54 } 55 if(i == 0) 56 { 57 for(j = 0; j < n/2; j++) 58 { 59 temp = arr[j]; 60 arr[j] = arr[n-1-j]; 61 arr[n-1-j] = temp; 62 } 63 } 64 65 } 66 int flag = 0; 67 for(i = 0; i < n; i++) 68 { 69 if(flag) printf(" "); 70 else flag = 1; 71 printf("%d",arr[i]); 72 } 73 printf("\n"); 74 delete [] arr; 75 } 76 return 0; 77 }