有N条绳子,它们的长度分别为Li。如果从它们中切割出K条长度相同的
绳子,这K条绳子每条最长能有多长?答案保留到小数点后2位。
输入格式:
第一行两个整数N和K,接下来N行,描述了每条绳子的长度Li。
输出格式:
切割后每条绳子的最大长度。
输入样例#1:
4 11
8.02
7.43
4.57
5.39
输出样例#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 }