信息学奥赛一本通 1242. 网线主管(二分答案)
原题链接
中等
作者:
orange0912
,
2021-06-05 17:45:24
,
所有人可见
,
阅读 707
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
using namespace std;
int d[10010];//厘米数组
int n,k;
double b;
int dmax=0;
//判断是否小段切分为mid的情况能达到k条
bool judge(int mid)
{
int res=0;
for(int i=1;i<=n;i++)
{
res+=d[i]/mid;
}
return res>=k;
}
int main( )
{
cin>>n>>k;
double w=0;
int l=0,r=0;
for(int i=1;i<=n;i++)
{
scanf("%lf",&b);
d[i]=(int)(b*100+0.5);//此处需要考虑精度问题
if(r<d[i])
r=d[i];
}
//上述结束循环后r即为最大的网线长度
//在0---r范围内二分答案
while(l<r)
{
int mid=(l+r+1)/2;//取中间值准备判断,下面更新l=mid,Y总模板 此处需要+1
if( judge(mid) ) //说明mid可以切出k段,答案可能比mid更大
l=mid;
else r=mid-1;
}
printf("%.2lf\n",l/100.0);
return 0;
}