首页 > 代码库 > POJ 1064 (二分)
POJ 1064 (二分)
题目链接: 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[10005];bool check(double x){ int cnt=0; for(int i=1;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=0,r=-1,ans=0; for(int i=1;i<=n;i++) { scanf("%lf",&cable[i]); r=max(r,cable[i]); } int L=0,R=r*100; while(L<=R) { int mid=L+(R-L)/2; if(check((double)mid/100)) {ans=mid;L=mid+1;} else R=mid-1; } ans/=100; 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 |
POJ 1064 (二分)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。