TransWikia.com

Задача на бинарный поиск по ответу

Stack Overflow на русском Asked on December 16, 2021

Имеется задача. Нужно по заданной высоте, ширине и количеству дипломов повесить их в квадратную рамку минимального размера. Если нужно, вот ссылка на задачу. Я написал код, и при попутке сдать его, из 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))
         

One Answer

Алгоритм выглядит правильным, но на кой вам хранить последовательные целые числа большого диапазона в списке?

Работайте с m, возвращайте r, а a[] вообще исключите.

Answered by MBo on December 16, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP