本文主要是介绍杭电OJ 1027：Ignatius and the Princess II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目的大意就是求一串数字的全排列的第m小的排列，比如1,2,3是3个数的最小的全排列，1,3,2是次小的全排列。这个题目可以用STL的一个函数next_permutation，这个函数是用来生成一个全排列的下一个全排列，当然也可以自己写生成排列算法，生成一个全排列的下一个全排列的算法如下：
（1）从数组最后一个开始往前找，假设后一个记为p，前一个记为pre，直到找到一个满足A[pre]<A[p]时停止。
（2）从数组的最后一个开始寻找第一个大于A[pre]的数字，记它的位置为plast。
（3）将A[pre]的值和A[plast]的值交换。
（4）将p以及p后的所有数据全部逆序排列。
下面的代码是自己根据上面的算法写的生成全排列的方法（已经AC）：
#include <stdio.h>
const int N=1010;
int arr[N];
bool nextPermutation(int input[],int n){int i=n-2;bool flag=false;for(i=n-2;i>=0;i--){if(arr[i]<arr[i+1]){flag=true;break;}}if(flag==false)return false;for(int j=n-1;j>=0;j--){if(arr[j]>arr[i]){int tmp=arr[j];arr[j]=arr[i];arr[i]=tmp;int count=(i+n)/2;for(int k=i+1;k<=count;k++){tmp=arr[k];arr[k]=arr[n-k+i];arr[n-k+i]=tmp;}break;}}return flag;
}
int main(){int m,n;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)arr[i]=i+1;if(m==1){printf("%d",arr[0]);for(int i=1;i<n;i++)printf(" %d",arr[i]);printf("\n");}else{m--;while(m--){nextPermutation(arr,n);}printf("%d",arr[0]);for(int i=1;i<n;i++)printf(" %d",arr[i]);printf("\n");}}return 0;
}下面附上使用STL版本的AC代码：
//using STL
//Accepted
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){int m,n;int arr[1010];while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)arr[i]=i+1;m--;while(m--){next_permutation(arr,arr+n);}printf("%d",arr[0]);for(int i=1;i<n;i++)printf(" %d",arr[i]);printf("\n");}return 0;
}这篇关于杭电OJ 1027：Ignatius and the Princess II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
