hdu 5122 （2014北京现场赛 K题）

把一个序列按从小到大排序要执行多少次操作

只需要从右往左统计，并且不断更新最小值，若当前数为最小值，则将最小值更新为当前数，否则sum+1

Sample Input
2
5
5 4 3 2 1
5
5 1 2 3 4

Sample Output
Case #1: 4
Case #2: 1

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <string>
 6 # include <cmath>
 7 # include <queue>
 8 # include <list>
 9 # define LL long long
10 using namespace std ;
11 
12 const int INF=0x3f3f3f3f;
13 
14 int a[1000010] ;
15 
16 int main()
17 {
18     //freopen("in.txt","r",stdin) ;
19     int T ;
20     scanf("%d" , &T) ;
21     int Case = 0 ;
22     while(T--)
23     {
24         Case++ ;
25         int n , i , j;
26         scanf("%d" , &n) ;
27         for (i = 0 ; i < n ; i++)
28             scanf("%d" , &a[i]) ;
29         int sum = 0 ;
30         int MIN = INF ;
31         for (i = n-1 ; i >=0 ; i--)
32         {
33             if (a[i] < MIN)
34                 MIN = a[i] ;
35             else
36                 sum++ ;
37         }
38         printf("Case #%d: %d
" , Case , sum) ;
39 
40 
41     }
42 
43     return 0 ;
44 }

View Code