POJ1064 Cable master（二分浮点误差）

题目链接：传送门

题目大意：

　　给出n根长度为1-1e5的电线，想要从中切割出k段等长的部分（不可拼接），问这个k段等长的电线最长可以是多长（保留两位小数向下取整）。

思路：

　　很裸的题意，二分答案即可。

　　但是如果使用double类型的二分会有浮点误差。

　　比如答案为2.50，二分的右区间r也为2.50时，则不管怎么二分，mid总是小于右区间的。也就是说mid最大只能取到2.50-eps/2 = 2.4999995，根据题意保留两位小数向下取整后的值就是2.49了。

　　因此对于这题的向下取整，在取整操作之前，可以加一个 += eps，就可以避免这种浮点误差了。

同样地如果一个题目要向上取整的话，可以加一个 -= eps，从而避免浮点误差。

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX_N = 1e4 + ;

const double eps = 1e-;

int n, k;

double a[MAX_N];

bool check(double mid) {

    int sum = ;

    for (int i = ; i <= n; i++) {

        sum += (int)(a[i]/mid);

    }

    return sum >= k;

}

int main()

{

    while (cin >> n >> k) {

        double sum = ;

        for (int i = ; i <= n; i++) {

            scanf("%lf", &a[i]);

            sum += a[i];

        }

        double ans = ;

        double l = , r = sum / k;

        while (r-l > eps) {

            double mid = l + (r - l) / 2.0;

            if (check(mid)) {

                ans = max(ans, mid);

                l = mid;

            }

            else {

                r = mid;

            }

        }

        ans += eps;

        ans = (int)(ans*)/100.0;

        printf("%.2f\n", ans);

    //    r = (int)(r*100)/100.0;

    //    printf("%.2f\n", r);

    }

    return ;

}

/*

4 11

8.02

7.43

4.57

5.39

4 14

5.99

8.00

8.00

6.00

2 5

5.99

0.99

*/

巴特西

POJ1064 Cable master（二分浮点误差）

最新文章

热门文章

巴特西

POJ1064 Cable master（二分 浮点误差）

最新文章

热门文章

POJ1064 Cable master（二分浮点误差）