分析
同y总视频讲解逻辑。根据分析,两种情况,【且每种情况都是减半】,二分查找即可。
代码
def check(mid):
res = 0
for i in range(n):
res += (h[i] // mid) * (w[i] // mid) #注:Py里需要打括号,计算顺序和cpp不同
if res >= k: return True
return False
def bisect(l, r):
while(l < r):
mid = (l + r + 1) >> 1 #加号优先级高于>> 可不加括号
if check(mid): l = mid
else: r = mid - 1
print(r)
if __name__ == '__main__':
n, k = map(int, input().split())
h = [0] * 100010
w = [0] * 100010
for i in range(n):
h[i], w[i] = map(int, input().split())
bisect(1, 100000)
更加好看的版本:
N, K = map(int, input().split())
MAX = 0
cakes = []
for _ in range(N):
w, h = map(int, input().split())
MAX = max(MAX, w, h)
cakes.append([w, h]) # 读二维数组更简单
def check(size):
cnt = 0
for w, h in cakes:
cnt += (h // size) * (w // size) #注:Py里需要打括号,计算顺序和cpp不同
return cnt
l, r = 0, MAX
while l < r:
mid = l + r + 1 >> 1
if check(mid) >= K: l = mid
else: r = mid - 1
print(l)
来自题解区