题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5122
解题报告：定义一种排序算法，每一轮可以随机找一个数，把这个数与后面的比这个数小的交换，一直往后判断，直到后面没有比这个数小的，这样称为一轮，现在给定一个长度为n的序列，要你求，至少要经过多少轮，可以使这个序列成为有序的。
由于只能跟后面的数进行比较，所以我只要统计后面的数有比这个数小的数的个数就可以了。从后往前扫一遍，每次更新当前最小的。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef __int64 INT; 8 const int maxn = 1e6+5; 9 10 int A[maxn]; 11 12 int main() 13 { 14 int T,n,kase = 1; 15 scanf("%d",&T); 16 while(T--) 17 { 18 scanf("%d",&n); 19 for(int i = 0;i < n;++i) 20 scanf("%d",&A[i]); 21 INT ans = 0; 22 int M = 0x7fffffff; 23 for(int i = n-1;i >= 0;--i) 24 { 25 if(M < A[i]) ans++; 26 M = min(M,A[i]); 27 } 28 printf("Case #%d: %I64d ",kase++,ans); 29 } 30 return 0; 31 }