洪水！（Flooded! ACM/ICPC World Final 1999,UVa815)

题目描述：竞赛入门经典的习题4-10

解题思路：1.把各个网格想象成一个数组

　　　　　2.排序

　　　　　3.雨水总体积去铺满

//太懒了只写了求海拔

 1 #include <stdio.h>
 2 #define maxn 50
 3 int altitude[maxn*maxn] ;int smr[maxn][maxn] ;
 4 int main(int argc, char *argv[])
 5 {
 6     int n,m,i ;
 7     while(scanf("%d%d",&n,&m) == 2 &n &m){
 8         //循环输入 
 9         for(i=0;i<n*m;i++) scanf("%d",&altitude[i]) ;
10         int water,count = i ; //网格数量
11         scanf("%d",&water) ;
12         //排序
13          for(int i=0;i<n*m-1;i++)
14              for(int j=0;j<n*m-1-i;j++)
15                  if(altitude[j]>altitude[j+1]){
16                      int t = altitude[j] ;
17                      altitude[j] = altitude[j+1] ;
18                      altitude[j+1] = t ;
19                  } 
20         //for(int i=0;i<n*m;i++) printf("%d     ",altitude[i]) ;
21         printf("
") ;
22         int i,lw ,flag=0,t=0;
23     
24         for(i=0;i<count-1;i++){
25             if(altitude[i+1]>altitude[i]){
26                 t = (i+1)*(altitude[i+1] - altitude[i])*10*10 + t ;
27                 if(t<=water) lw = t ;
28                 else{
29                     flag = 1;
30                     break ;
31                 }        
32             }
33             if(flag) break ;
34             //printf("%d  ",lw);
35         } 
36         //printf("
%d",i) ;
37         //printf("
%d",altitude[i]) ;
38         printf("
%f",altitude[i]+(float)(water - lw)/((i+1)*100)) ;
39     }    
40     return 0;
41 }