Задача на бинарный поиск по ответу
Имеется задача. Нужно по заданной высоте, ширине и количеству дипломов повесить их в квадратную рамку минимального размера. Если нужно, вот ссылка на задачу. Я написал код, и при попутке сдать его, из 21 теста 11 тестов не проходят из-за привышения лимита памяти. Объясните, что я сделал не так.
import math
h,w,n = map(int,input().split())
# размер рамки, от рамки, для которой условие точно не
# выполниться, до рамки для который условие точно выполниться.
ans = [i for i in range(1,math.ceil(math.sqrt(n))*(max(w,h))+1)]
def bin_search(a,x,w,h):#обычний бин. поиск по ответу
l = 0
r = len(a)-1
m = (l+r)//2
while r - l >1:
m = (l+r)//2
if (a[m] // w) * (a[m] // h) >= n:
r = m
else:
l = m
return a[r]
print(bin_search(ans,n,w,h))
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Алгоритм выглядит правильным, но на кой вам хранить последовательные целые числа большого диапазона в списке?
Работайте с m, возвращайте r, а a[] вообще исключите.