Бинарный поиск по ответу

Question

Не проходит по памяти скорее всего из-за большого списка, но я не знаю как короче его ещё сделать

from math import *


def binarnui_poisk(a,w,h): # модифицированный левый бинарный поиск
    result= -1
    low = 0
    high = len(a) - 1
    mid = len(a) // 2

    while low <= high:
        if a[mid] // w >= w and a[mid] // h >= h:

            high = mid - 1
            result = a[mid]

        else:
            low = mid + 1


        mid = (low + high) // 2


    return result

w, h, n = map(int, input().split())
s = sqrt((w * h * n)) # нахожу корень от площади, чтобы дальше с ним рабоатать, он будети началом списка
s = ceil(s) # округляю до целого числа
result_ = binarnui_poisk([int(i) for i in range(s, s * w * h + 1) ],w,h)
print(result_)

Answer 1

Список вам вовсе не нужен. Бинарный поиск по ответу не подразумевает, что вы генерируете все возможные ответы, и ищете в них подходящий. Просто используете значение в заданных пределах - ведь у вас, скажем, a[mid] - это всего лишь mid + startvalue.

И условие поиска я поправил (хотя тщательно не проверял) - ваше же совсем игнорировало количество дипломов n

def binarnui_poisk(lo, hi, w,h, n): # модифицированный левый бинарный поиск
    result= -1
    mid = (lo + hi) // 2

    while lo <= hi:
        if (mid // w) * (mid // h) >= n:

            hi = mid - 1
            result = mid

        else:
            lo = mid + 1


        mid = (lo + hi) // 2


    return result

w, h, n = map(int, input().split())
result_ = binarnui_poisk(0, n*w*h + 1, w, h, n)
print(result_)

БЛОГ НА HUSL

Бинарный поиск по ответу

Ответы (1 шт):