140_割绳子问题 Cable master (POJ No.1064)

 有N条绳子，他们的长度分别为L_i。如果从他们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多少？

 用二分搜索法就可以解决，重点是他要规定收敛次数，而不是收敛的差值。规定收敛差值太小的话，可能会导致收敛困难。

//
//  140_cable master.cpp
//  changlle
//
//  Created by user on 1/8/16.
//  Copyright (c) 2016 user. All rights reserved.
//

#include <iostream>
using namespace std;
const int INF=100;

int N=4;
int K=11;
double L[4]={8.02,7.43,4.53,5.39};

bool C (double x) {

    int num=0;

    for (int i=0;i<N;i++)
        num+=L[i]/x;

    return num>=K;
}


double solve (){

    double lb=0;
    double ub=INF;
    double mib=0;

    for (int i=0;i<100;i++){

        mib=(lb+ub)/2;

        if (C(mib))
            lb=mib;
        else
            ub=mib;

    }

    return mib;
}


int main() {

    cout<<solve()<<endl;



    return 0;
}