在考虑题目的时候从正面考虑比较困难, 因为我们需要考虑两个问题。
一个是需要切多长,一个是要满足需要切几份。
而我们可以考虑把最优解问题转化为,判断型问题,这样就能简单许多。
我们可以假设如果我们知道绳子需要切成多长例如为x
,然后对每段绳子除以x
,累加总和后看是否大于等于需要切成的数量。
那现在就剩下一个问题了如何求x
,那我们就可以通过对区间分割的方式也就是二分的方式来进行确定。
代码详解
#include <cstdio>
const int N = 100010;
int arr[N];
int n, m;
/**
* 用来确定需要舍去哪个区间
* bool check(double mid)
* @param mid
* @return true
*/
bool check(double mid) {
int s = 0;
for (int i = 0; i < n; ++ i) {
// 查看在mid的时候绳子可以分为几份
s += arr[i] / mid;
// 如果大于需要分的数量,就说明mid值小了,舍去左半边
if (s >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++ i) {
scanf("%d", &arr[i]);
}
// 参考使用浮点数二分,寻超出合适长度
double l = 0, r = 1e9;
// 在浮点数二分的时候,二分到l-r>1e-(k+2),注意k表示的是精确到第几位
while(r - l > 1e-4) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", r);
return 0;
}