首页 > > 程序设计 > C/C++ >

P1577 切绳子

2018-06-17 22:00:34来源：未知阅读 ()

题目描述

有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的

绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位。

输入输出格式

输入格式：

第一行两个整数N和K，接下来N行，描述了每条绳子的长度Li。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

2.00

比较好想的一个二分答案题

楼下说了一种先乘再除的思路，

我来发一份c++代码。

提醒大家几个问题：

1.如果你是61分，那么请把右边界开大一点。（我一开始还以为爆int了233）

2.如果你是92分&&RE了一个点，请在二分答案的时候加上一句：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define lli long long int 
 4 using namespace std;
 5 const int MAXN=10000001;
 6 inline void read(int &n)
 7 {
 8     char c=getchar();bool flag=0;n=0;
 9     while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();
10     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();
11 }
12 int n,k;
13 int a[MAXN];
14 int pd(int val)
15 {
16     int sum=0;
17     for(int i=1;i<=n;i++)    sum+=a[i]/val;
18     return sum>=k;
19 }
20 int main()
21 {
22     read(n);read(k);
23     for(int i=1;i<=n;i++)
24     {    double p;scanf("%lf",&p);    a[i]=p*100;    }    
25     int l=0,r=100000000,ans=0;
26     while(l<=r)
27     {
28         int  mid=l+r>>1;
29         if(mid==0)    break;
30         if(pd(mid))    l=mid+1,ans=mid;
31         else r=mid-1;
32     }
33     printf("%.2lf",(double)ans/100);
34      return 0;
35 }