思路:
使用二分法,判断能否剪出要求的绳子数量。
二分的是剪出的绳子长度。
开始状态:$\color{red}{l = 0, r = 1e9, mid = (l + r) / 2。}$
判断能总共剪出长度为 mid 的绳子多少根:$\color{red}{总共能剪出的根数 = 每一根绳子能剪出的根数之和。}$
$\color{red}{如果能剪出长度为 mid 的绳子,则 l = mid ,如果不能,则 r = mid。}$
$\color{red}{直到 r - l < 1e-3。}$
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n,m;
bool check(double len)//剪长度为 len 的绳字是否能到 m 根
{
int res = 0;
for (int i = 0; i < n; i++)
{
res += a[i] / len;//一根绳子能剪出多少长度为 m 的绳子
if (res >= m) return true;
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
double l = 0, r = 1e9;
while (r - l > 1e-3)//二分法
{
double mid = l + (r - l) / 2;
if (check(mid)) l = mid;//若能剪出 mid 长度的
else r = mid;
}
printf("%.2f", l);
}
有问题发在评论,会及时回复
求个点赞~
关于二分法的理解,可以看下这个: https://mp.weixin.qq.com/s/3fjDhS3lb5CBrzx6p0XIxw
请教,为什么double mid = l + (r - l) / 2;这一步需要加上 l 呢 ?
个人习惯,两数之和可能溢出
(l+r)/2 加法可能溢出。所以换成了 l+(r-l)/2
好的,谢谢你!
tql
while (r - l > 1e-3)
中不能大于1e-6不然会超时,太坑了,我平时取的是1e-8我也是
while (r - l > 1e-3)
中不能大于1e-6不然会超时,太坑了,我平时取的是1e-8您好请问一下为什么
r
不可以设置为sum(a[i]) / m
呢?为什么用float
类型存数据会超时?谢谢!Float精度不够,二分可能死循环,平均值也是
多谢
r = *max_element(a,a+n);
l和r 处理边界有啥讲究没呀? 为什么这里都可以直接赋值为mid ?
可以看下题解最后的链接或者y总的模板,讲的比较清楚
请问一下二分法为什么要r-l>1e-3?
浮点数二分,用r-l>1e-3。
请教,为什么l、r、mid我用float类型会超时。
容易出错的有两个
代码有些地方打错了,比如 i 打成了l,j 打成了 r。
跳出二分时,r - l 设置的过小。
第一个可能性大一些
通不过的用例,是不是数值比较大
好像是,我傻了😂,感谢大佬
刚试了下,的确,float 的精度有限,数值过大时候,不能通过
请问下,这里的跳出循环的条件怎么想的?
浮点数二分,两数之差小于精度要求时跳出。不是自己想出来的,学来的
学到了,谢谢!!
请教下,这是怎么想到要二分绳子长度的?
最先想到的肯定是从穷举,根据穷举,想想二分法能用不,发现能用。
先枚举一下mid,把每一个mid是否满足条件都输出,如果能发现一个点,左边都不能满足,右边都能满足,那就能二分。
1 序列有序 查找中间的一个转折点 基本都可以用二分,
2 甚至序列不完全有序 比如有序数组旋转了以下 查找某个数 也可以用二分。
第2种情况可以见 acwing 22. 旋转数组的最小数字
二段性