HDU5122

 1 #include <stdio.h>
 2 #include <string.h>
 3 int s[1011010];
 4 int main()
 5 {
 6     int T,sum,n,f;
 7     scanf("%d",&T);
 8     f=0;
 9     while(T--)
10     {
11         f++;
12         scanf("%d",&n);
13         for(int i=0;i<n;i++)
14         {
15             scanf("%d",&s[i]);
16         }
17         int min1=s[n-1];
18         sum=0;
19         for(int i=n-2;i>=0;i--)
20         {
21             if(s[i]<min1)
22             {
23                 min1=s[i];
24             }
25             else
26             {
27                 sum++;
28             }
29         }
30         printf("Case #%d: %d
",f,sum);
31     }
32     return 0;
33 }

View Code

这道题的做法很微妙，要想让遍历次数最少，从右向左扫一遍，如果比当前的最小值大，round++；

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5122