二分法解决 “最大化平均值问题”

题目描述

有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位（去尾法）。 示例： 输入：([8.02,7.43,4.57,5.39],11) 输出：2.00 解释： 列表[8.02,7.43,4.57,5.39]表示每段绳子的长度，11表示切割成长度相等的11段，求出每小段绳子的最长距离是2.00

编程思路

       首先确定初始区间[left，right] ，显然left=0，right可取单段绳子的最大值。        然后使用二分法公式mid=(left+right)/2得到mid，把mid假定是切割后的每段长度。如果按照mid值可以切出k段绳子，说明mid可能过小，则增大下界，使left=mid；如果按照mid值切不出k段绳子，则mid取大了，减小上界，使right=mid。        循环，最终使left 与right无限逼近答案。 注意：程序中可以使用 while ((right-left)>=1e-4)作为循环控制条件。 python代码如下

def panduan(L,mid): #L是原始绳子列表 n=0 #n是可分割的段数 for i in L: n+=i//mid return n def func(L,k): #k是要求分割的段数 left=0 right=max(L) while (right-left)>=1e-4: mid=(left+right)/2 if panduan(L,mid)>=k: left=mid if panduan(L,mid)<k: right=mid return "%.2f" % left print(func([8.02,7.43,4.57,5.39],11))

输出结果

2.00