首页 > 代码库 > POJ 1833 排序
POJ 1833 排序
http://poj.org/problem?id=1833
题意：
给出一个排序，求出它之后的第k个排序。
思路：
排序原理：
1、如果全部为逆序时，说明已经全部排完了，此时回到1~n的排序。
2、从后往前找到第一对 ai<ai+1,然后从i+1~n寻找比ai大的最小的数并与之互换，之后再对i+1~n的数进行排序即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 10 const int maxn=105;11 12 int n,k;13 int a[1025];14 15 void solve()16 {17 int i;18 for(i=n-2;i>=0;i--)19 if(a[i]<a[i+1]) break;20 if(i==-1)21 {22 sort(a,a+n);23 return;24 }25 int MIN=0x3f3f3f;26 int k;27 for(int j=i+1;j<n;j++)28 {29 if(a[j]>a[i] && a[j]<MIN)30 {31 MIN=a[j];32 k=j;33 }34 }35 36 int temp=a[i];37 a[i]=a[k];38 a[k]=temp;39 40 sort(a+i+1,a+n);41 }42 43 44 int main()45 {46 //freopen("D:\\input.txt","r",stdin);47 int T;48 scanf("%d",&T);49 while(T--)50 {51 scanf("%d%d",&n,&k);52 for(int i=0;i<n;i++)53 scanf("%d",&a[i]);54 while(k--) solve();55 for(int i=0;i<n;i++)56 {57 if(i) printf(" ");58 printf("%d",a[i]);59 }60 printf("\n");61 }62 }
POJ 1833 排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。