Երկուական որոնում պատասխանի վրա – Ծառերը հնարավորինս նոսր տնկել

Մուտք

Ելք

Օրինակներ

Բացատրություն

Ուղեցույց

• Պետք է կարողանանք ստուգել, թե արդյոք թեկնածու պատասխանը բավարարում է առաջադրանքի պահանջնրին (այստեղ — մեզ անհրաժեշտ է ստուգել, թե արդյոք կարելի է տնկել ծառերը այնպես, որ դրանք լինեն իրարից նվազագույնը d հեռավորության վրա)։

• Ստուգող ֆունկցիա def check(x):-ը պետք է վերադարձնի True, եթե հնարավոր է տվյալ թեկնածու պատասխանի դեպքում բավարարել խնդրի պահանջը, և False հակառակ դեպքում։

• Տարբեր արժեքների (երկուական որոնման ընթացքում) ստուգման արդյունքներն ունեն երկու հիմնական կառուցվածք.
• False False False True True (Հնարավոր չէ առաջին մի քանի թվի համար և հետո հնարավոր է մնացած ավելի մեծ թվերի համար)։ Այս դեպքում մենք ման փնտրում ենք առաջին True արժեքը՝ ամենափոքր արժեքը, որի դեպքում խնդրի պահանջը բավարարում է։
• True True True True False False (հնարավոր է փոքր թվերի համար իսկ հետո հնարավոր չէ մեծերի դեպքում)։ Այս դեպքում մենք ման փնտրում ենք վերջին True արժեքը՝ ամենամեծ արժեքը, որի դեպքում խնդրի պահանջը բավարարվում է։
Մեր խնդրում ցանկանում ենք, որ ծառերը տնկվեն հնարավորինս նոսր, այսինքն՝ նվազագույն հեռավորությունը լինի որքան հնարավոր է մեծ։ Եթե որոշակի մեծություն x-ով հնարավոր է տնկիները տեղակայել, ուրեմն ավելի փոքր արժեքների դեպքում նույնպես հնարավոր կլինի դա անել (ավելի խիտ տարբերակով)։

n, t = ...
x = sorted(x)

def check(d):
    """ Ստուգում է, թե արդյոք կարելի է տնկել t ծառեր, որպեսզի դրանց միջև հեռավորությունը լինի նվազագույնը d """
    planted = 0               # Պետք է տնկենք t ծառ (այժմ տնկված է 0)
    prev = float('-inf')      # Նախորդ տնկված ծառի կոորդինատը
    for xi in x:
        if xi - prev >= d:    # Եթե xi կոորդինատում կարելի է տնկել նոր ծառ
            planted += 1
            prev = xi
    return planted >= t

l, r = 1, max(x)         
while r - l > 1:         
    mid = (l + r) // 2   
    if check(mid):       
        l = mid
    else:                
        r = mid

print(l)