DLU-1036 最强雨女传说

 1 #include <stdio.h>
 2  
 3 int trap(int* height, int heightSize)
 4 {
 5     int rains = 0;
 6     if(heightSize==0)
 7         return rains;
 8     int leftmax = 0,rightmax = 0;
 9     int left = 0,right = heightSize-1;
10     while(left<right)
11     {
12         leftmax = leftmax>height[left]?leftmax:height[left];
13         rightmax = rightmax>height[right]?rightmax:height[right];
14  
15         if(leftmax<rightmax)
16         {
17             rains += leftmax-height[left];
18             left ++;
19         }
20         else
21         {
22             rains += rightmax-height[right];
23             right --;
24         }
25     }
26     return rains;
27 }
28  
29 int main()
30 {
31     int heightSize;
32     while(~scanf("%d",&heightSize))
33     {
34         int height[heightSize];
35         int i;
36         for(i = 0;i < heightSize;i ++)
37         {
38             scanf("%d",&height[i]);
39         }
40         int result = trap(height, heightSize);
41         printf("%d
",result);
42     }
43     return 0;
44 }