Как можно оптимизировать код в данной задаче? Использую алгоритм бинарного поиска по ответу

Рейтинг: 1Ответов: 1Опубликовано: 04.03.2023

В классе учатся N человек. Классный руководитель получил указание направить на субботник R бригад по С человек в каждой.

Все бригады на субботнике будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.

Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по три человека в каждой. Тогда одним из вариантов является такой:

1 бригада: люди с ростом 225, 205, 225

2 бригада: люди с ростом 160, 190, 170

При этом число неудобства первой бригады будет равно 20, а число неудобства второй — 30. Максимальное из чисел неудобств будет 30, и это будет наилучший возможный результат.

n,r,c=map(int,str(input()).split())
mass=[]
for i in range(n):
    mass.append(int(input()))
mass=sorted(mass)
right=max(mass)-min(mass)
left=0
while left<right:
    m=(left+right)//2
    j=0
    k=0
    while j+c-1<len(mass):#считываю сколько бригад получится при разнице максимального и минимального роста m
        if mass[j+c-1]-mass[j]<=m:
            k=k+1
            j=j+c
        else:
            j=j+1
    if k>=r:
        right=m
    else:
        left=m+1
print(right)

Проходит 17 тестов, на 18 - привышен лимит времени исполнения. Ограничение 2 секунды. Результат 18 теста 2.083

python
Источник: Stack Overflow на русском

Ответы

▲ 2

Разобрался, позабыл что поиск максимума и минимума массива проходит за O(n).

 n,r,c=map(int,str(input()).split())
    mass=[]
    for i in range(n):
        mass.append(int(input()))
    mass=sorted(mass)
    right=mass[len(mass)-1]-mass[0]
    left=0
    while left<right:
        m=(left+right)//2
        j=0
        k=0
        while j+c-1<len(mass):#считываю сколько бригад получится при разнице максимального и минимального роста m
            if mass[j+c-1]-mass[j]<=m:
                k=k+1
                j=j+c
            else:
                j=j+1
        if k>=r:
            right=m
        else:
            left=m+1
    print(right)