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