Бинарный поиск по ответу. Задача на поиск максимальной длины

Question

Есть n веревочек, нужно нарезать из них k кусков одинаковой длины. Найдите максимальную длину кусков, которые можно получить.

Входные данные В первой строке заданы два числа — n и k (1≤n,k≤10000 ). Далее в каждой из последующих n строк записано по одному числу — длине очередной веревочки ai (1≤ai≤107 ).

Выходные данные Выведите одно вещественное число — максимальную длину кусков, которые можно получить. Ответ будет считаться верным, если относительная или абсолютная погрешность не превышает 10−6 .

Пример

Входные данные

4 11
802
743
457
539

Выходные данные
200.5

n, k = map(int, input().split())
def bina_(sp,n,k): # поиск целого числа
    i = 0
    r = 10 ** 7 + 1
    while r > i + 1:
        sr = (i + r) // 2
        if proveri_(sr,sp,k) == 1:
            i = sr
        else:
            r = sr
    return i

def bina_s(sp,a,k): # поиск числа после точки
    i = 0
    r = 9999999999
    while r > i + 1:
        sr = (i + r) // 2
        if proveri_s(sp,a,k,sr) == 1:
            i = sr
        else:
            r = sr
    return i
def proveri_s(sp,a,k,sr):
    co_ = 0
    for i in sp:
        co_ += int(i // float(f'{a}.{sr}'))
    if co_ >= k:
        return 1

def proveri_(sr,sp,k):
    co_ = 0
    for i in sp:
        co_ += (i // sr)
    if co_ >= k:
        return 1

sp = []
for i in range(n):
    sp.append(int(input()))
    
a = bina_(sp,n,k)
b = bina_s(sp,a,k)
print(float(f'{a}.{b}'))

Упростил код

n, k = map(int, input().split())
def bina_(sp,n,k):
    i = 1
    r = 10 ** 7 + 1
    for _ in range(1000):
        sr = (i + r) / 2
        if proveri_(sr,sp,k) == 1:
            i = sr
        else:
            r = sr
    return i

def proveri_(sr,sp,k):
    co_ = 0
    for i in sp:
        co_ += (i // sr)
    if co_ >= k:
        return 1

sp = []
for i in range(n):
    sp.append(int(input()))

a = bina_(sp,n,k)
print(a)

Answer 1

Первый код не искал относительную или абсолютную погрешность не превышающую 10−6 Измененный код: относительную или абсолютную погрешность реализовал через for _ in range(100):

    i = 0
    r = 10 ** 7 + 1
    for _ in range(100):
        sr = (i + r) / 2
        if proveri_(sr,sp,k) == 1:
            i = sr
        else:
            r = sr
    return i

def proveri_(sr,sp,k):
    co_ = 0
    for i in sp:
        co_ += (i // sr)
    if co_ >= k:
        return 1


a = bina_(sp,n,k)
print(a)

Answer 2

Цикл бинарного поиска по условию должен работать, пока относительная или абсолютная погрешность не станет меньше или равной одной миллионной. А погрешность в данном случае - ширина оставшегося диапазона (делённая на верхнюю границу для относительной погрешности)

i = 0
r = 10 ** 7 + 1
while ((r-i)/r > 1E-6) and (r-i > 1E-6):

БЛОГ НА HUSL

Бинарный поиск по ответу. Задача на поиск максимальной длины

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