主页 / 问题 / 1595748
Accepted
user27630724
Asked:2024-10-05 17:46:22 +0800 CST2024-10-05 17:46:22 +0800 CST

按答案进行二分查找

  • 772

它无法凭记忆运行，很可能是因为列表太大，但我不知道还有什么办法可以使它更短 问题情况

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_)

在此输入图像描述

python

1 个回答

  1. Best Answer

    你根本不需要清单。按答案进行二分搜索并不意味着您生成所有可能的答案并在其中搜索合适的答案。只需使用给定限制内的值 - 毕竟，例如，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_)
    • 3

相关问题