POJ - 网线主管摘要本题要求在 N 根长度已知的网线中切割出 K 根等长的网线求最长可行的等长长度精确到厘米。该问题具有单调性可采用二分答案法求解——在长度区间内二分搜索验证能否切出不少于 K 段。全文分别给出浮点二分与整数二分两种解法并详细讲解精度控制、四舍五入陷阱、整数二分边界等关键注意事项。题目描述仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。为购买网线裁判委员会联系了当地的一个网络解决方案提供商要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好这样选手们之间的距离可以尽可能远一些。该公司的网线主管承接了这个任务。他知道库存中每条网线的长度精确到厘米并且只要告诉他所需的网线长度精确到厘米他都能够完成对网线的切割工作。但是这次所需的网线长度并不知道这让网线主管不知所措。你需要编写一个程序帮助网线主管确定一个最长的网线长度并且按此长度对库存中的网线进行切割能够得到指定数量的网线。输入第一行包含两个整数N和K以单个空格隔开。N1 N 10000是库存中的网线数K1 K 10000是需要的网线数量。接下来N行每行一个数为库存中每条网线的长度单位米。所有网线的长度至少1m至多100km。输入中的所有长度都精确到厘米即保留到小数点后两位。输出网线主管能够从库存的网线中切出指定数量的网线的最长长度单位米。必须精确到厘米即保留到小数点后两位。若无法得到长度至少为1cm的指定数量的网线则必须输出“0.00”不包含引号。样例输入4 11 8.02 7.43 4.57 5.39样例输出2.00来源Northeastern Europe 2001思路要点这道题的本质是一个最优化问题 我们手头有n nn个浮点数代表原始网线长度现在需要找出一个最大的浮点数x xx代表切出来的单根网线长度使得这n nn个数分别除以x xx向下取整后的总和大于或等于给定的常数k kk。 简而言之把n nn根长网线切成k kk根等长的短网线求网线的最长长度。如果切不出哪怕 1cm 的长度就输出 0.00。关键思路遇到最优化问题首先要思考这个问题的答案是否具有“单调性”试想一下如果我们打算切出来的网线长度x xx很短比如只有 1cm那么我们能切出来的总根数肯定非常多容易满足≥ k \ge k≥k的条件 反之如果x xx非常长比如直接取库存里最长的那根我们能切出来的总根数可能就达不到k kk根。因此答案存在一个临界点长度在某一个值及以下时段数够超过这个值段数就不够。这种“非此即彼”的单调分界特性正是二分查找法这里也称为二分答案的标准应用场景。由于本题涉及两种不同的单位因此二分方法也不唯一两者的区别在于对“空间”的切入视角不同思路一浮点数二分直接逼近法直接在“米”的连续实数空间[0.01, maxa]里进行搜索。它通过控制循环次数或设定一个极小的微量如1e-6作为结束条件。优点是直观、不需要转换单位缺点是最后输出时需要小心翼翼地处理系统自带的四舍五入。思路二整数二分单位转换法利用题目中“精确到厘米小数点后两位”的关键信息将所有数据统一乘以 100把问题直接放缩到“厘米”的离散整数空间[1, maxa * 100]里。这样就变成了在整数序列中找最大可行值。优点是逻辑严密完全规避了浮点数四舍五入的边界特例缺点是读入和计算段数时需要注意数据类型的转换。解题步骤我们以题目给定的样例输入n 4 n 4n4,k 11 k 11k11库存数组a { 8.02 , 7.43 , 4.57 , 5.39 } a \{8.02, 7.43, 4.57, 5.39\}a{8.02,7.43,4.57,5.39}为例模拟代码的执行过程变量定义与初始化定义变量n, k存储网线数和需求数。定义浮点型数组a[maxn]存储库存网线长度maxa记录最长网线sum记录总长度。读入数据并预处理读取 4 和 11此时n 4k 11。循环读取数组累加sum 25.41找到最大值maxa 8.02。特判提前剪枝判断sum * 100 k即把所有的网线全部切成最小单位 1cm总数够不够k kk根当前总计 2541cm大于 11所以继续往下走。如果不满足直接输出 0.00 并结束程序时间复杂度达到O ( 1 ) O(1)O(1)的极简。二分查找核心逻辑设定答案的搜索区间下界l 0.01最小长度上界r 8.02即maxa因为不可能切出比最长库存还要长的一段。 设定精度条件r - l 1e-6只要区间长度大于这个极小值就继续二分。第 1 轮二分计算中间值mid (l r) / 2此时mid 4.015。定义变量s 0记录能切出的段数。遍历数组分别计算每根网线能切几段8.02 / 4.015 向下取整为 17.43 / 4.015 向下取整为 14.57 / 4.015 向下取整为 15.39 / 4.015 向下取整为 1累加得到s 4。判断s k(4 11)说明切得太长了段数不够。因此缩小上限r mid即r 4.015。第 2 轮二分当前区间[0.01, 4.015]。计算mid (0.01 4.015) / 2此时mid 2.0125。再次遍历数组计算能切的段数8.02 / 2.0125 取整为 37.43 / 2.0125 取整为 34.57 / 2.0125 取整为 25.39 / 2.0125 取整为 2累加得到s 10。判断s k(10 11)依然不够。继续缩小上限r mid即r 2.0125。第 3 轮及后续二分经过多次不断折半mid会趋近于真实的最大合法值即恰好能切 11 段的临界值。当mid 2.00时我们会发现能切出4 3 2 2 11 4 3 2 2 11432211段满足条件此时程序会执行l mid尝试是否还能“再长一点点”。最终当r和l的差距缩小到1e-6以内时循环结束。此时r停留在大约 2.005 左右的值。格式化截断输出执行printf(%.2lf, floor(r * 100.0) / 100);。假设此时r 2.005乘以 100 变成 200.5。 调用floor向下取整变成 200.0。 除以 100 变成 2.00。输出结果2.00。避开了系统默认的四舍五入。参考代码-浮点二分解法浮点二分注意事项精度的控制要点提醒普通的输出语句printf(%.2lf, r);自带四舍五入属性。举个例子如果二分查找到的极限长度是 2.005 米四舍五入后输出 2.01 米。但拿着 2.01 米回去切很可能根本切不出k kk段所以这里必须是向下取整截断。代码中floor(r * 100.0) / 100是本题最终能拿满分的关键。浮点数二分循环结束条件要点提醒浮点二分不能写while(l r)因为浮点数是无限逼近的。一般来说题目要求保留M MM位小数我们的精度就要开到10 − ( M 2 ) 10^{-(M2)}10−(M2)甚至更高本题保留 2 位小数使用1e-6或1e-7非常稳妥。大数据的防爆处理要点提醒切分出来的段数求和变量s定义为long long。虽然本题k ≤ 10000 k \le 10000k≤10000但如果测试数据非常极端比如几万根 100km 的网线切成 1cm 的小段累计段数极有可能会超过int的最大值2 × 10 9 2 \times 10^92×109使用long long可以在各种恶劣数据下保证万无一失。#includebits/stdc.h#definemaxn10005usingnamespacestd;intn,k;doublea[maxn],maxa,sum;intmain(){scanf(%d %d,n,k);for(inti1;in;i){scanf(%lf,a[i]);suma[i];maxamax(maxa,a[i]);// 动态记录最长的一根作为二分的右边界}// 特判如果把所有网线连起来都切不出k根1cm的直接输出0.00if(sum*100k){printf(0.00\n);return0;}// 二分答案在区间 [0.01, maxa] 中找最大长度doublel0.01,rmaxa;while(r-l1e-6){// 浮点数二分的精度控制1e-6是个安全的经验值doublemid(lr)/2;longlongs0;// s记录当前mid长度下能切出的总段数for(inti1;in;i){sfloor(a[i]/mid);}if(sk){rmid;// 切的段数少了说明mid猜得太长了缩小右边界}else{lmid;// 切的段数够了s k看看绳子是不是还可以再长一点}}// 关键易错点防范题目要求“精确到厘米”且隐含要求是“截断”而非四舍五入// 通过 floor(r * 100.0) / 100 强制舍去小数点后两位之后的部分printf(%.2lf\n,floor(r*100.0)/100);return0;}参考代码-整数二分解法整数二分注意事项为什么最终答案是r而不是l要点提醒在我们的设计中当s k时说明当前长度可行我们执行了l mid 1去找更大的。这就意味着每当找到一个可行解l就会跑到它的右边去。因此当循环结束l跑到了r的右边时l代表的是第一个不可行的过大值而r则顺理成章地停留在了最后一个可行的最大值上。#includebits/stdc.h#definemaxn10005usingnamespacestd;intn,k;doublea[maxn],maxa,sum;intmain(){// 读入基本数据scanf(%d %d,n,k);for(inti1;in;i){scanf(%lf,a[i]);suma[i];maxamax(maxa,a[i]);}// 全局可行性特判if(sum*100k){printf(0.00\n);return0;}maxa*100;// 核心思想把最大米数统一转换成厘米单位化浮点为整数intl1,rmaxa;// 标准整数二分模板查找满足条件的最大值while(lr){intmid(lr)1;// 位运算优化的除以2longlongs0;for(inti1;in;i){sfloor(a[i]*100.0/mid);// 计算在mid(厘米)长度下能切出的总段数}if(sk){rmid-1;// 段数不够说明单根网线太长了往左边找缩小右边界}else{lmid1;// 段数够了(s k)说明当前长度可行尝试往右边找更大的可能}}// 此时 r 刚好停留在最后一个合法的整厘米数上直接除以100.0无损还原并格式化输出printf(%.2lf\n,r/100.0);return0;}两种思路对比比较维度思路一浮点数二分思路二整数二分化浮为整思维难度低直接按照题目字面意思写。中等需要多一步单位换算和公式推导。代码边界需设定1e-6等死循环控制条件。采用标准while(l r)无死循环风险。输出处理必须配合floor(r * 100.0) / 100防四舍五入。直接r / 100.0干净输出无精度陷阱。竞赛推荐适合追求快速出码、保留小数位数极多的情况。推荐小数位数固定时此法最为稳健。