Searching on the Answer (Binary Search on Answer) — பதிலில் இருமை தேடல்

பதிலில் இருமை தேடல் — வெற்று விசை; சாத்தியம் monotone எனில் binary search.

உண்மை உலகில் இது ஏன் முக்கியம்?

ஆலை — குறைந்த வரி எண். QoS — தாமத வரம்பு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

feasible(x); lo,hi,mid; சிறிய சாத்திய x.

Pythonில் முயற்சி செய்வோம்

def min_k_for_sum_at_least(target: int, max_chunk: int) -> int:
    lo, hi = 1, target
    while lo < hi:
        mid = (lo + hi) // 2
        if mid * max_chunk >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo


print(min_k_for_sum_at_least(100, 30))

அடிக்கடி நேரும் தவறுகள்

• hi/lo வெளியே.
• சாத்திய சோதனை மந்தம்.

முக்கியச் சுருக்கக் குறிப்புகள்

• monotone நிரூபணம் முதலில்.
• ஒரே சாத்திய செயல்பாடு.