砍树问题(二分法)
程序员文章站
2024-03-16 09:00:34
...
题目描述森林里有n棵高高低低的树木,伐木工阿强接到老板的通知,需要k段等长的木材,阿强为了能挣更多钱,所以砍的木材要尽可能的长,所以引出一个问题,阿强最长能砍到多长的木材。
输入
第一行输入n和k,n表示n棵树木,k表示老板需要k段木材。(1<=n<=100,1<=k<=100)
第二行输入n个数,第i个数表示第i棵树的高度。(1<=树的高度<=100000000)
输出阿强最长能砍到的木材的长度。(精确到小数点后两位)
样例输入
3 4
3 5 4
样例输出
2.50
题解:这道题我一开始是暴力,因为当时还不会二分法,然后直接就超时,后来看算法书发现这道题原来是用二分的。这道题就是找不断通过二分法找k值,然后从存树的数组头到尾计算每棵树能砍多少长度为k的木头。但是要注意的是不能找到一个num == k 就直接break,因为像样例在找到2.47的时候也符合 num == k,所以一定要把条件设置为 (right-left)>0.0002。0.002其实题中已经给你提示了。代码如下
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int n, k;
cin >> n >> k;
double a[n];
for (int i=0; i<n; i++)
{
cin >> a[i];
}
double left = 0, right = INF, mid = 0;
while ((right-left)>0.002)
{
mid = (left+right)/2;
int num = 0;
for (int i=0; i<n; i++)
{
num+=a[i]/mid;
}
if (num < k)
right = mid;
else if (mid >= k) //一定要有等号
left = mid;
}
printf("%0.2lf", mid);
return 0;
}
上一篇: 二分查找法-JAVA源码