题目链接: http://poj.org/problem?id=1064
题目大意：一堆棍子可以截取，问要求最后给出K根等长棍子，求每根棍子的最大长度。保留2位小数。如果小于0.01，则输出0.00
解题思路：
根据最长的棍子二分枚举切割长度。
这点很容易想到。
本题麻烦的地方在于小数的二分。
由于精度丢失问题，如果直接使用double进行二分，那么二分确定的最大长度必然是不精确的。
如：只有1根100.0的棍子，分成10段。如果使用double二分，那么就算把精度控制到0.0000001，
最后的答案也就9.9999666。，而不是10.
由于只要求2位小数，则把所有棍子长度*100，变成整数二分即可。
最后答案ans/=100。
#include "cstdio"
#include "iostream"
using namespace std;
int n,k;
double cable[];
bool check(double x)
{
int cnt=;
for(int i=;i<=n;i++) cnt+= (cable[i]/x);
if(cnt>=k) return true;
else return false;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
double l=,r=-,ans=;
for(int i=;i<=n;i++)
{
scanf("%lf",&cable[i]);
r=max(r,cable[i]);
}
int L=,R=r*;
while(L<=R)
{
int mid=L+(R-L)/;
if(check((double)mid/)) {ans=mid;L=mid+;}
else R=mid-;
}
ans/=;
if(ans<0.01) printf("0.00\n");
else printf("%.2lf",ans);
}
| 13589456 | neopenx | 1064 | Accepted | 252K | 63MS | C++ | 700B | 2014-11-01 20:39:43 |