Каков наиболее эффективный способ поиска оптимального здания для запуска ракеты? - PullRequest
Новая
       11

Каков наиболее эффективный способ поиска оптимального здания для запуска ракеты?

0 голосов
/ 21 ноября 2018

В настоящее время я работаю над алгоритмами с целью улучшения моих навыков.Прямо сейчас я застрял с проблемой, которую я не могу выбросить из головы.
Это выглядит так:

Я получаю 100 наборов конфигураций, каждая из которых содержит массив чисел, которые напоминаютвысота небоскреба.Теперь мне нужно найти небесный скребок в этом массиве, который позволяет с наилучшей точки зрения запускать ракету.
При условии, что все последующие здания должны быть выше (не могут быть одинаковой высоты), чем то, с которого они началивысота первого здания после небоскреба, с которого запускается ракета, не имеет значения.Что имеет значение, так это высота следующих зданий.

Например: 

Input: 5 4 3 4 5

Наилучший небоскрёб для запуска - 3, потому что есть всего 4 небоскреба, которые имеютвид на этот небоскреб.

Вывод будет 4

У меня есть реализация O (n ^ 2), но она слишком медленная для обработки тысяч скребков неба ... 

# read all configurations
while configs > 0:
    count = int(input())
    h = list(map(int, str(input()).split()))

    if buildings_count > 1:
        if allValuesAreSame(h):
            results.append(2 if count > 2 else 1)
        else:
            places = [0 for x in range(buildings_count)]

            for sample_index in range(count):
                last_high = -1
                for i in range(count):
                    if i == sample_index:
                        last_high = -1
                    else:
                        if i < sample_index:
                            if last_high == -1:
                                last_high = h[i]
                                places[sample_index] += 1
                            else:
                                if h[i] < last_high:
                                    last_high = h[i]
                                    places[sample_index] += 1
                        elif i > sample_index:
                            if last_high == -1:
                                last_high = h[i]
                                places[sample_index] += 1
                            else:
                                if h[i] > last_high:
                                    last_high = h[i]
                                    places[sample_index] += 1

        results.append(max(places))
    else:
        results.append(0)

    print(f'{results[-1]}')
    configs -= 1

Кто-нибудь знает, как оптимизировать этот алгоритм?Я работаю над этим уже несколько дней и не знаю, как его оптимизировать.

1 Ответ

0 голосов
/ 21 ноября 2018

Подсчитайте последовательность убывающих зданий, ведущих к данному зданию, затем посчитайте последовательность возрастающих.Сохраните сумму убывающей полосы и возрастающей полосы.Это должно позволить O (n)

Примерно в псевдокоде: 

decreasing = 0
increasing = 0
best = 0

for building in buildings:

    if building< last_building:
        decreasing +=1
    else
        past_decreasing = decreasing
        decreasing =0 

    if building > last_building:
        increasing +=1
    else:
        past_increasing = increasing
        increasing =0 

    if past_increasing+past_decreasing >best
         best = past_increasing+past_decreasing

Этот или некоторый вариант идеи должен позволять вам выполнять цикл только один раз.

...