首页 > 代码库 > 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