【题目描述】

有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位（直接舍掉2位后的小数）。

【输入描述】

第一行两个整数N和K（0<N<=10000， 0<K<=10000），接下来N行，描述了每条绳子的长度Li（0<Li<=100000.00）。

【输出描述】

切割后每条绳子的最大长度。

【样例输入】

4 11  8.02  7.43  4.57  5.39

【样例输出】

2.00

【题目分析】

  先确定初始区间[left，right]，显然left=0，right可取单段绳子的最大值，然后使用二分法得到mid，测试mid是大于要求的值还是小于要求的值。如果mid值可以切出k段绳子，则增大下界，使left=mid；如果mid值切不出k段绳子，则mid取大了，减小上界，使right=mid；.然后最终使left 与right无限逼近答案。注意：程序中可以使用 while ((right-left)>1e-4)作为循环控制条件。

【参考代码】

#include <bits/stdc++.h>  double a[10001];  int n,k;  int judge(double x)  {             int num = 0,i;           for (i = 0; i < n; i++)                     num += (int)(a[i] / x);           return num;  }  int main()  {      int i;      double left,right,mid,max=0;  	scanf("%d%d",&n,&k);      for(i=0;i<n;i++)      {              scanf("%lf",&a[i]);              if (max<a[i])   				max=a[i];      }      left=0, right=max;      while ((right-left)>1e-4)      {          mid=(left+right)/2;          if(judge(mid)>=k)               left=mid;          else               right=mid;      }      printf("%.2f\n",floor(right*100)/100);      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});