首页 > 代码库 > poj1064 Cable master
poj1064 Cable master
Cable master
POJ - 1064
题目大意：
有N条绳子，它们的长度分别为Li。如果从他们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？答案保留到小数点后2位
二分答案：
可以认为是最大化最小值，答案范围左右边界分别为0和最长绳子的长度
不知道为什么在check(mid)=1的时候ans=mid最后输出的ans不一定是最优解
一组可以卡死这种做法的数据：
6 10
7.35 6.27 3.69 4.44 2.17 8.37
（标准输出2.45，错误输出2.44）
必须要在结果中输出r才行
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define maxn 100100using namespace std;double l,r,a[maxn];int N,K;double Max(double x,double y){return x>y?x:y;}bool check(double x){ int cnt=0; for(int i=1;i<=N;i++){ cnt+=floor(a[i]/x); } if(cnt>=K)return 1; else return 0;}int main(){ scanf("%d%d",&N,&K); for(int i=1;i<=N;i++){ scanf("%lf",&a[i]); r=Max(r,a[i]); } while(r-l>0.001){ double mid=(l+r)/2.0; if(check(mid))l=mid; else r=mid; } printf("%.2f",floor(r*100)/100);}
poj1064 Cable master
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。