首页 > 代码库 > HDU 5122 K.Bro Sorting(2014北京区域赛现场赛K题 模拟)

HDU 5122 K.Bro Sorting(2014北京区域赛现场赛K题 模拟)

题目链接: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\n",kase++,ans);29     }30     return 0;31 }
View Code

 

HDU 5122 K.Bro Sorting(2014北京区域赛现场赛K题 模拟)