AcWing 680. 算法基础班--第一章--4.浮点数二分模板
原题链接
简单
作者:
初静
,
2021-01-22 16:43:29
,
所有人可见
,
阅读 336
算法基础班–第一章–4.浮点数二分模板
算法模板(和整数二分一起记)
bool check(double x) // 检查x是否满足某种性质
{
...
}
double bsearch_3(double l, double r) {
const double eps = 1e-6; // eps表示精度,取决于题目对精度的要求
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
注意:
- 答案保留k位小数,二分时,只要区间长度小于 10 ^ -(k+2) 即可
- check()后,是 r=mid 还是 l=mid,取决于题目
- return l; 和 return r; 是一样的
本题完整代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
bool check(double mid) { //求的是: 一共可以切多少条长度为mid的绳子
int cnt = 0;
for (int i = 0; i < n; i++)
cnt += w[i] / mid;
return cnt >= m;
}
int main() {
cin >> n >>m; // n , m 绳子个数和需裁剪的数量
for (int i = 0; i < n; i++) cin >> w[i];
double l = 0, r = 1e9;
while (r - l > 1e-4) { // 区间长度大于 1e-4,求下中点 // for (int i = 0; i < 100; i++) { 改成这句话也是正确的(笔记本P10.acwing)
double mid = (l + r) / 2; // double 不可以用 >> 操作
if (check(mid)) l = mid; // 本题求的是 这M根绳子的最长长度,所以应尽可能的让 区间取大点
else r = mid;
}
printf("%.2lf\n", l); // l 和 r 一样,非常接近
return 0;
}