切绳子

淡淡的烟草味﹌ 2022-04-03 02:45 325阅读 0赞

###  ###

题目描述

有n条绳子，长度分别为L\[i\]。如果从他们中切割出k条长度相同的绳子的话，这k条绳子每条最长能有多长？（答案保留小数点后两位，规定1单位长度的绳子最多可以切割成100份）

输入

输入n,k,（1<=n,k<=10000）

然后n行，输入L\[i\],代表每一条绳子的长度(1<=L\[i\]<=100000)

输出

切出k条长度相等的绳子最大长度是多少，输出保留两位小数

样例输入

4 11  
8.02  
7.43  
4.57  
5.39

样例输出

2.00

##### 分析： #####

本题的基本思路。我们可以运用二分查找法。我们可以用二分查找，查找到一个数，将其中每条绳子与之相除得到能剪成多少根绳子。算出总的绳子数。然后，比较判断。如果绳子数大于等于需要的绳子数，那么我们可以继续二分，不过将起点改成之前的中点（即上次的查找长度）。如果，绳子数小于需要的绳子数，我们继续二分，不过将其终点改成上次查找的中点。继续查找。

#include"stdio.h"
    #include"string.h"
    
    double Serch(double Rope[],long long k,long long N)
    {
        long long i,j=0;
        long long count=0;
        //这里的Min_leght赋值成一个很大的数；
        //之所以不用最小的那个绳子的长度。是因为有可能不需要对最小绳子进行操作。
        //即其他绳子能够剪出长度大于最小绳子的长度的可能性。
        //所以Min_leght=1000000.0而不是最小绳子的长度。
        double Min_leght=1000000.0,Mid_leght=Rope[0]/2,end_leght,strat_leght=0;
        //这里的精度极高，而且易出错，推荐直接执行100次循环就好了，就可以不用考虑精度
        while(Min_leght-strat_leght>=0.00000000000002)
        {  Mid_leght=(Min_leght+strat_leght)/2;
            for(i=0;i<N;i++)
            {
                count+=(long long)(Rope[i]/Mid_leght);
            }
            if(count>=k)
                strat_leght=Mid_leght;
            else
                Min_leght=Mid_leght;
           // printf("count=%lld\n",count);
            count=0;
        }
      return Mid_leght;
    }
    int main()
    {
        long long n,k;
        double Rope[10001],T,leght;
        long long i,j,count;
        while(~scanf("%lld%lld",&n,&k))
        {
            for(i=0;i<n;i++)
                scanf("%lf",&Rope[i]);
    
            leght=Serch(Rope,k,n);
            printf("%0.2lf\n",(long long )(leght*100)/100.0);
    
        }
    }