切绳子题解（博客搬家）

题目

题目描述

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

输入

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

输出

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

样例输入

4 11 8.02 7.43 4.57 5.39

样例输出

2.00

提示

对于100%的数据 0<Li<=100000.00 0<n<=10000 0<k<=10000

分析题目

最近在做二分题解，作为一道经典的二分题，切绳子是一定要会的。 这道题与木材加工有些相似，但这里出现了浮点数，又要比木材加工复杂一些。 又因为它最多只有两个小数点，所以，我们可以直接把输入的数乘100，把浮点数变为整数就行了。 当然，输出时又要除100，再变为浮点数。

double ans=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lf",&a[i]); a[i]*=100; ans+=a[i]; }

这里我用了一个特判，防止输出时输不出0.00。（我不写上去时WA了）

if(ans*100<k){ printf("0.00"); return 0; }

进入正轨，开始二分。 二分怎么写知道吧？ 左右两指针，取中点缩小范围。直到左指针大于等于右指针，得出答案。

int l=0,r=10000001; while(l<=r) { m=(l+r)/2; if(m==0) break;//这里又需要一个特判，不过可能没用，因为我前面已经特判0的情况了。 if(js(m)) l=m+1; else r=m-1; }

再让我们看看函数 $js$ 中有些什么?

inline bool js(int x) { long long t=0; for(register int i=1;i<=n;i++) t+=a[i]/x; return t>=k; }

我们把每根绳子可以割出的段数累加，与要求段数比较， 如果符合条件，说明切割后每条绳子的最大长度可能大于当前中点的大小，将左指针移至中点再继续找下一个中点。 如果不符合条件，说明切割后每条绳子的最大长度可能小于当前中点的大小，将右指针移至中点再继续找下一个中点。

code

#include <bits/stdc++.h> using namespace std; double a[100001]; int sum; int k,m,n; inline bool js(int x) { long long t=0; for(register int i=1;i<=n;i++) t+=a[i]/x; return t>=k; } int main() { double ans=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lf",&a[i]); a[i]*=100; ans+=a[i]; } if(ans*100<k){ printf("0.00"); return 0; } int l=0,r=10000001; while(l<=r) { m=(l+r)/2; if(m==0) break; if(js(m)) l=m+1; else r=m-1; } printf("%.2lf",(l-1)/100.0); return 0; }