poj1064二分搜索的应用

时间:2023-01-06 04:22:57
//题意:给定N条绳子长度分别为Li,如果从中切割出K跳长度相同的绳子这K跳绳子每条最长多少
//思路:floor(L/X)是否大于或者等用于K


//228K 141MS


#include <iostream>
#include <math.h>
using namespace std;
#define  MAX_N  10005

 int N,K;
double L[MAX_N];


bool C(double x){
	int num = 0;
    for (int i=0;i<N;++i)
     num += (int)(L[i]/x);
	return num>=K;
}

int main(){
	double lb =0;

	scanf("%d %d",&N,&K);
	double ub = 0;
	for (int i=0;i<N;++i){
	 scanf("%lf",&L[i]);
	 if (L[i]>ub)
	  ub = L[i];
	}
	//一次循环范围缩小一半100次精度达到10-30次方
	for (int i=0;i<100;++i)
	{
		double mid = (lb+ub)/2;
		if (C(mid))
		  lb = mid;
		else
		  ub = mid;
	}

	printf("%.2lf\n",floor(ub*100)/100);

	return 0;
}