Python-сообщество

Всем привет. В очередной раз обращаюсь к вам за советом. Задачу решил, но на неизвестных входных данных проверка выдает 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)

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

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

Отредактировано Arsenii (Авг. 18, 2017 17:28:35)

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

 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)

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

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

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

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

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

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

Arsenii

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

Отредактировано doza_and (Авг. 21, 2017 09:43:44)