【二分+贪心】用 N 根绳子裁剪出 M 根等长绳子

有 N 根绳子，第 i 根绳子的长度为 l[i]，现在需要 M 根等长的绳子。
你可以对这 N 根绳子进行任意裁剪（不能拼接），请你计算出这 M 根绳子最长的长度。
输入描述：
  第一行包括两个整数 N, M，含义如题所述(1 <= N, M <= 100000)
  第二行包含N个整数，分别对应N根绳子的长度(0 < l[i] < 10⁹)
输出描述：
  一个数字，表示裁剪后最长的长度，保留两位小数

示例输入：
3 4
3 5 4
示例输出：2.50
解释： 第一根和第三根绳子分别裁剪出一根 2.50 长的绳子，第二根绳子刚好可以裁剪出两根 2.50 的长绳子，共 4 根。

  这道题其实就是问裁剪出 M 段等长绳子，最大裁剪长度是多少。像这样的 "找到一个数，它要满足一定条件" 的题目，第一反应就是 贪心+二分，比如 “公路建设加油站，使最小距离最大化” 这道题以及现在这道题。这道题就是找到一个长度值 X，使得 X 满足能够从已有的 N 根绳子中裁剪出来 M 段。
  思路明确了，代码就比较好写了，注意因为不是整数的 l 和 r，所以判断条件从 r &gt; = l r &gt;= l r>=l 变成 r − l &gt; e p s r - l &gt; eps r−l>eps，eps是一个自己设的数，比如 1e-6：

#include <iostream>
#include <vector>
using namespace std;

bool check_len(double len, const vector<int>& ropes, int target) {
	int cnt = 0;
	for(const int& r : ropes) {
		cnt += r / len;
		if (cnt >= target) return true;
	}
	return false;
}

int main() {
	int n, m, total_len = 0;
	cin >> n >> m;
	vector<int> ropes(n);
	for (int i = 0; i < n; ++i) {
		cin >> ropes[i];
		total_len += ropes[i];
	}
	double l = 0, r = total_len;
	while(r - l > 1e-6) {
		const double mid = l + (r - l) / 2.0;
		printf("l = %lf, r = %lf, mid = %lf\n", l, r, mid);
		if (check_len(mid, ropes, m)) l = mid;
		else                          r = mid;
	}
	printf("%.2f\n", r);
	return 0;
}

  运行结果如下：

3 4
3 5 4
l = 0.000000, r = 12.000000, mid = 6.000000
l = 0.000000, r = 6.000000, mid = 3.000000
l = 0.000000, r = 3.000000, mid = 1.500000
l = 1.500000, r = 3.000000, mid = 2.250000
l = 2.250000, r = 3.000000, mid = 2.625000
l = 2.250000, r = 2.625000, mid = 2.437500
l = 2.437500, r = 2.625000, mid = 2.531250
l = 2.437500, r = 2.531250, mid = 2.484375
l = 2.484375, r = 2.531250, mid = 2.507813
l = 2.484375, r = 2.507813, mid = 2.496094
l = 2.496094, r = 2.507813, mid = 2.501953
l = 2.496094, r = 2.501953, mid = 2.499023
l = 2.499023, r = 2.501953, mid = 2.500488
l = 2.499023, r = 2.500488, mid = 2.499756
l = 2.499756, r = 2.500488, mid = 2.500122
l = 2.499756, r = 2.500122, mid = 2.499939
l = 2.499939, r = 2.500122, mid = 2.500031
l = 2.499939, r = 2.500031, mid = 2.499985
l = 2.499985, r = 2.500031, mid = 2.500008
l = 2.499985, r = 2.500008, mid = 2.499996
l = 2.499996, r = 2.500008, mid = 2.500002
l = 2.499996, r = 2.500002, mid = 2.499999
l = 2.499999, r = 2.500002, mid = 2.500000
l = 2.499999, r = 2.500000, mid = 2.500000
2.50