Flooded!-二分答案/模拟
		update@2011-12-02
		           /**
  *返回0表示x==0,返回-1表示 x < 0, 返回1表示 x > 0
  *accuracy(a-b) == 0, a == b 或者 fabs(a-b) < eps
  *accuracy(a-b) != 0, a != b 或者 fabs(a-b) > eps
  *accuracy(a-b) <  0, a <  b 或者 a - b < -eps
  *accuracy(a-b) >  0, a >  b 或者 a - b > eps
  *accuracy(a-b) <= 0, a <= b 或者 a - b < eps
  *accuracy(a-b) >= 0, a >= b 或者 a - b > -eps
  */
 #define eps 1e-12
 int accuracy(double x){ return x < -eps?-1:((x < eps)?0:1);}
 int isOk(double x){
     //尝试这个高度
     double total = 0;
     for(int i = 0;i < m;i++){
         for(int j = 0; j < n;j++){
             if(accuracy(x-square[i][j]) > 0){
                 total += 100*(x - square[i][j]);
             }
         }
     }
     return accuracy(total-all);
 }
 double binaryTrial(double left,double right){
     double mid;
     while(accuracy(left-right) < 0){
         mid = (left + right)*1.0/2;
         int t  = isOk(mid);
         if(t <= 0){left = mid;}
         else{right = mid;}
     }
     return mid;
 }
题目链接:
Flooded!简单的二分答案,被精度卡到吐了,一直WA....后来又仔细弄了下精度..注意水的体积为0的情况。另一个解法,排序然后模拟..更直接,更简单。