【二分法】分巧克力问题/python

1.看出是用二分法：

最大值最小化，最小值最大化，满足条件的最值，用二分法做。

2.确定low,high,确定check的条件

3.注意：

  是当low<high的时候进行循环，当相等或大于的时候输出，while的条件不能写错。

  本题是在区间里面找满足条件的最大值，所以，在算mid的时候面对取整的问题让它向大的值取。check过mid是满足条件后，low=mid,这样low是满足条件的，下一个找的区间里面一定有满足条件的值。如果mid不满足条件，high=mid-1，区间里没有这个不满足条件的数，不会影响结果。如果low=mid+1,那么low可能不满足条件，high也可能不满足条件，有可能就在一个没有答案的区间里找。

  同理，如果是找满足条件的最小值，mid就要往小的取整，保证high满足条件，check(mid)之后，若满足，high=mid,不满足，low=mid-1。

#满足条件的最大边长，用二分法
n,k=map(int,input().split())
h=[]
w=[]
for _ in range(n):
          wi,hi=map(int,input().split())
          h.append(hi)
          w.append(wi)

def check(x):#如果x够分了说明满足条件
          cnt=0
          for i in range(n):
                    cnt+=(h[i]//x)*(w[i]//x)
          return cnt>=k

low=1
high=max(max(h),max(w))
while low<high:
          mid=(low+high+ 1)//2# 使用+1确保mid偏向high方向，避免死循环
          if check(mid):#如果mid满足条件，就去找找有没有更大的数满足条件,所以low前移
                    low=mid#low=mid+1是错的
          else:
                    high=mid-1

# 最后low=high输出哪个都一样
print(high)