DjangoBB LoFi version

Полная версия: Задача "Гражданская оборона"

Начало » Центр помощи » Задача "Гражданская оборона"

Arsenii

Авг. 17, 2017 23:16:07

Всем привет. В очередной раз обращаюсь к вам за советом. Задачу решил, но на неизвестных входных данных проверка выдает Time limit exceeded. Нужна помощь по сокращению времени выполнения программы. Есть непроверенная инфа, что в этом тесте цифры очень большие. Вот текст задачи и мое решение.

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.

Формат ввода

В первой строке вводится число n - количество селений (1 <= n <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Формат вывода

Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

Указание

Создайте список кортежей из пар (позиция селения, его номер в исходном списке), а также аналогичный список для бомбоубежищ. Отсортируйте эти списки.

Перебирайте селения в порядке возрастания.

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

Для хранения ответа используйте список, где индекс будет номером селения, а по этому индексу будет запоминаться номер бомбоубежища.

 n = int(input())
nlist = list(map(int, input().split()))
m = int(input())
mlist = list(map(int, input().split()))
c = []
c1 = []
for i in range(n):
    camp = (nlist[i], i + 1)
    c.append(camp)
    c.sort()
    c1 = c.copy()
b = []
for j in range(m):
    bomb = (mlist[j], j + 1)
    b.append(bomb)
b.sort()
z = 0
for k in range(n):
    x = 999999
    y = 0
    a = c[k][1] - 1
    for h in range(z, m):
        if abs(c[k][0] - b[h][0]) < x:
            x = abs(c[k][0] - b[h][0])
            y = b[h][1]
            z = h
        else:
            break
    c1[a] = y
print(*c1)

Просьба не предлагать свои решения, нужен только совет по оптимизации моего. Заранее спасибо!

krok64

Авг. 18, 2017 08:13:20

У тебя массив b отсортирован, значит ищи в нем значения бинарным поиском. И задай начальное значение x=10**10 т.к. по условию максимальное расстояние может быть равно 10**9

Arsenii

Авг. 18, 2017 17:27:56

krok64
Нам это объяснено не было (бинарный поиск). Нашел в инете суть, ничего не получается реализовать, т.к. условие не в равенстве числу, а в уменьшении разности расстояний до бомбоубежищ при увеличении индекса… Это я туплю, или это и правда не так просто?

Arsenii

Авг. 19, 2017 14:25:25

Попробовал использовать бинарный поиск. Как смог, как удалось подогнать - написал. Не проходит все равно тот же тест по времени. Что допилить(или как написать новый)?

 n = int(input())
nlist = list(map(int, input().split()))
m = int(input())
mlist = list(map(int, input().split()))
c = []
c1 = []
for i in range(n):
    camp = (nlist[i], i + 1)
    c.append(camp)
    c.sort()
    c1 = c.copy()
b = []
for j in range(m):
    bomb = (mlist[j], j + 1)
    b.append(bomb)
b.sort()
for k in range(n):
    g = 0
    h = m // 2
    f = m
    a = c[k][1] - 1
    x = 10**10
    if c[k][0] < b[0][0]:
        c1[a] = b[0][1]
    elif c[k][0] > b[m - 1][0]:
        c1[a] = b[m - 1][1]
    else:
        while g < f and h != 0 and h != m - 1:
            if b[h - 1][0] <= c[k][0] <= b[h][0]:
                break
            elif c[k][0] > b[h][0]:
                g = h + 1
            else:
                f = h - 1
            z = h
            h = ((g + f) // 2)
        if g < f:
            if abs(b[h - 1][0] - c[k][0]) > abs(b[h][0] - c[k][0]):
                c1[a] = b[h][1]
            else:
                c1[a] = b[h - 1][1]
        elif c[k][0] < b[0][0]:
            c1[a] = b[0][1]
        elif c[k][0] > b[m - 1][0]:
            c1[a] = b[m - 1][1]
        else:
            c1[a] = b[z + 1][1]
print(*c1)

krok64

Авг. 21, 2017 08:49:07

Вынеси из цикла сортировку и и копирование списка. Т.к. при больших n тут могут быть тормоза

 for i in range(n):
    camp = (nlist[i], i + 1)
    c.append(camp)
    c.sort()
    c1 = c.copy()

Arsenii

Авг. 21, 2017 09:42:18

krok64
Спасибо, это по невнимательности. Все равно на том же тесте та же ошибка time limit exceeded(

doza_and

Авг. 21, 2017 09:42:24

Arsenii
Просьба не предлагать свои решения

Однако что менять то можно?

Arsenii
Что допилить(или как написать новый)?

Эволюция однако…

Arsenii
Это я туплю, или это и правда не так просто?

Arsenii

 while g < f and h != 0 and h != m - 1:

Тупите. Главное нормальный алгоритм. Малыми изменениями не обойдешься.
Могу предложить следующее упрощение алгоритма
Сортируете оба списка.
создаете список середин между бомбоубежищами. Дальше ведете поиск от последнего селения вперед пока не превысите следующую середину. При заданных условиях вполне возможно что линейный поиск будет быстрее. Это немного лишних вычислений, но существенно упростит логику алгоритма.