1、从左边开始,找到一个满足左边小于自己的数a
2、从这个数a开始向右找,找到一个最小的比a打的数,两者交换
3、把从a开始向右的所有数用qsort从小到大排个序
#include <iostream> using namespace std; void nextPermutation(int a[],int n); int myCompare(const void *a,const void *b); void exchange(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } void nextPermutation(int a[],int n) { int i; for(i=n;i>0&&a[i-1]>a[i];i--); if(i==0) { for(i=1;i<=n;i++) a[i]=i; return; } int j,*min; min=&a[i]; for(j=i+1;j<=n;j++) { if(*min>a[j]&&a[j]>a[i-1]) min=&a[j]; } exchange(a+i-1,min); qsort(a+i,n-i+1,sizeof(int),myCompare); } int myCompare(const void *a,const void *b) { return *((int*)a)-*((int*)b); } int main() { int a[1024]; int n,k; int N,i; a[0]=2000; scanf("%d",&N); while(N--) { scanf("%d%d",&n,&k); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=0;i<k;i++) nextPermutation(a,n); for(i=1;i<=n-1;i++) cout<<a[i]<<" "; cout<<a[n]<<endl; } }
1000MS正好AC
下面这个是用的STL的库函数 耍流氓
#include <iostream> #include <iterator> #include <algorithm> using namespace std; int main() { int a[1024]; int n,k; int N; scanf("%d",&N); while(N--) { scanf("%d%d",&n,&k); int i; for(i=1;i<=n;i++) scanf("%d",&a[i]); int *start=a+1; int *end=a+n+1; for(i=0;i<k;i++) next_permutation(start,end); for(i=1;i<=n-1;i++) cout<<a[i]<<" "; cout<<a[n]<<endl; } }