yukicoder No.67 よくある棒を切る問題 (1)

問題

問題概要

条件を満たす最大の値を求める問題。

解法

求める棒の長さは条件を満たす最大の値であり、その値より棒の長さを短くしても条件を満たすが、それより大きくすると条件を満たさなくなる。よって、このような場合は、二分探索をして効率よく求める棒の長さが求まる。
今回の問題で注意しなければならないのは答えがdouble型。int型の場合、r - l > 1の間２分探索を続けるような形で、実装すればよいが、double型の場合、答えが大きくなると、単に絶対誤差のみで、r - l > 1e-10のような形でやろうと思うと、無限ループに入ってしまう。そのため、簡単にかくなら、ループを十分な回数回すような実装にするのが楽。 しっかりやるなら、相対誤差ってのを使えばいいらしい。

ミス

無限ループには気を付けたいですね。

コード

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

ll n, L[200010];
ll k;

bool hantei(double m){
    ll sum = 0;
    rep(i, n){
        sum += floor((double)L[i] / m);
        if(sum >= k) return true;
    }
    return false;
}

int main(void){
    cin >> n;
    rep(i, n) cin >> L[i];
    cin >> k;

    //2分探索
    double r = 1e10 + 1, l = 0.0;
    int cnt = 0;
    while(r - l > 1e-10 && cnt < 100){
        cnt++;
        double mid = (l + r) / 2.0;
        if(hantei(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }

    printf("%.10f\n", l);
    return 0;
}