Cable master POJ - 1064
二分
题目描述：仓库中有N条光缆，要求把它们截成总共K段等长的光缆，求截取的每段光缆的最大长度。
解题思路：比较水的二分，就是精度坑人+读题费劲。注意这个题精度要求特别高，另外输出的时候因考虑到实际因素，保留两位小数的时候是把两位之后的数据截掉，并不是默认的四舍五入，所以用到了floor函数。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cmath>
using namespace std;
const int maxn=10000+10;
const double esp=1e-9;
int m,n;
double cable[maxn];
void solve()
{
sort(cable,cable+m);
double r=cable[m-1],l=0.0;
int cnt;
for(int i=0;i<100;i++)
{
double mid=(l+r)/2;
cnt=0;
for(int i=0;i<m;i++)
{
cnt+=(int)(cable[i]/mid);
}
if(cnt>=n) l=mid;
else r=mid;
}
printf("%.2lf",floor(l*100)/100);
}
int main()
{
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++)
{
scanf("%lf",&cable[i]);
}
solve();
return 0;
}
一般的二分,二分一百次精度基本上就非常精确了。此题中floor的运用也是长经验了。
东软集团开奖3人在聊