140_ロープ切り問題ケーブルマスター(POJ No.1064)
845 ワード
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
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=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<