Flooded!-二分答案/模拟

update@2011-12-02
C++语言: 高亮代码由发芽网提供

/**
*返回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的情况。另一个解法,排序然后模拟..更直接,更简单。