分割绳子（二分）

分割绳子

时间限制: 1 Sec  内存限制: 128 MB

题目描述

现有N条绳子，它们的长度分别为L1，L2，„„，Ln，如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？

输入

共有两行，第一行包含两个正整数N和K，用一个空格分隔；第二行包含N个数，依次表示N条绳子的长度，两数间用一个空格分隔。每条绳子长度的小数不超过两位。（1<=N<=1000，1<=K<=1000，1<=Li<=10000）

输出

仅包含一个数，表示所得K绳子的最大长度。答案四舍五入保留小数点后两位。

样例输入

复制样例数据

4 11
8.02 7.43 4.57 5.39

样例输出

2.00

简单的一到二分题，先把一根中分k条的最大值找出当做l，然后最大化能分的就是正好总值/k做为r，然后判断是否可以分成k根，如果分不够，说明取得值太大，l = mid,够分或者多了（！！注意等号的位置），r = mid;

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const double eps = 1e-8;
int n, k;
double a[1005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d", &n, &k);
	double sum = 0, l = 0, r;
	for (int i = 1; i <= n; i++){
		scanf("%lf", &a[i]);
		sum += a[i];
		l = max(l, a[i] / k);
	}
	r = sum / k;
	while(fabs(r - l) > eps){
		double mid = (r + l) / 2;
		int num = 0;
		for (int i = 1; i <= n; i++){
			num += a[i] / mid;
		}
		if(num >= k){
			l = mid;
		}else{
			r = mid;
		}
	}
	printf("%.2lf\n", l);

	return 0;
}
/**/

最后注意下精度问题就行了