OpenJudge / Poj 1833 排列 C++
链接地址:
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 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。