这道题主要的陷阱在于使用二分法找r的时候,存在更新r使得r<=l或者更新l>=r的情况,但这个时候代指r的变量是min,在此时while通过判断推出循环,l或r的值与mid不一致,得到的结果不是r,同时由于使用的是二分,mid的值的变化不是递增或递减的,由于判断条件仅需满足res>k,因此最后一次得到的结果可能存在不是最大的情况(未证明),所以将每次的结果存入列表,最后输出最大值
样例
import os
import sys
res = 0
h = []
w = []
cnt = []
n, k = map(int, input().split( ))
for i in range(n):
a, b = list(map(int, input().split( )))
h.append(a)
w.append(b)
l = 0
r = max(max(h),max(w))
pos = 0
while(l <= r): #!
mid = (l + r + 1) >> 1
#print("mid",mid)
for i in range(n):
if w[i] >= mid and h[i] >= mid:
res += (w[i]//mid)*(h[i]//mid)
#print("res:",res)
if res >= k:
l = mid + 1
cnt.append(mid)
else:
r = mid - 1
res = 0
print(max(cnt))