Не проходят все тесты, выводит не тот результат, решаю через алгоритм двух указателей

Рейтинг: 0Ответов: 2Опубликовано: 19.02.2023

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

В наличии имеется N (1 ≤ N ≤ 100 000) маек и M (1 ≤ M ≤ 100 000) штанов, про каждый элемент известен его цвет (целое число от 1 до 10 000 000). Помогите Глебу выбрать одну майку и одни штаны так, чтобы разница в их цвете была как можно меньше.

Формат ввода Сначала вводится информация о майках: в первой строке целое число N (1 ≤ N ≤ 100 000) и во второй N целых чисел от 1 до 10 000 000 — цвета имеющихся в наличии маек. Гарантируется, что номера цветов идут в возрастающем порядке (в частности, цвета никаких двух маек не совпадают).

Далее в том же формате идёт описание штанов: их количество M (1 ≤ M ≤ 100 000) и в следующей строке M целых чисел от 1 до 10 000 000 в возрастающем порядке — цвета штанов.

Формат вывода Выведите пару неотрицательных чисел — цвет майки и цвет штанов, которые следует выбрать Глебу. Если вариантов выбора несколько, выведите любой из них.

n=int(input())
s=str(input()).split()
mayki=list(map(lambda x: int(x), s))
m=int(input())
z=str(input()).split()
pants=list(map(lambda x: int(x),z))
last=0
k=100000122
for first in range(n):
    while last<len(pants) and abs(mayki[first]-pants[last])<=k:  
        k=abs(mayki[first]-pants[last])
        answer=[mayki[first],pants[last]]
        last=last+1
print(*answer)
python
Источник: Stack Overflow на русском

Ответы

▲ 0

Тут можно взять алгоритм - двух указателей

n = int(input())
tshirts = list(map(int, input().split()))

m = int(input())
pants = list(map(int, input().split()))

tshirts.sort()
pants.sort()

i, j = 0, 0
min_diff = float('inf')

while i < n and j < m:
    diff = abs(tshirts[i] - pants[j])
    if diff < min_diff:
        min_diff = diff
        tshirt_color = tshirts[i]
        pants_color = pants[j]

    if tshirts[i] < pants[j]:
        i += 1
    else:
        j += 1

print(tshirt_color, pants_color)
▲ 0

Вариант с бинарным поиском

lines = ['5', '2 50 75 100 120',
         '5', '12 33 74 77 118']
def input(): # эмуляция ввода чисел
    global lines
    return lines.pop(0)


n = int(input())
s = str(input()).split()
mayki = list(map(lambda x: int(x), s))
m = int(input())
z = str(input()).split()
pants = list(map(lambda x: int(x), z))

answer = []
delta_min = None
for color in mayki:
    first, last, ldelta, rdelta = 0, len(pants) - 1, 0, 0
    while last - first > 1:
        pos = int((first + last) // 2)
        if pants[pos] > color:
            last = pos
        else:
            first = pos
    ldelta = abs(color - pants[first])
    rdelta = abs(color - pants[last])
    if ldelta < rdelta:
        answer.append((ldelta, color, pants[first]))
    else:
        answer.append((rdelta, color, pants[last]))

answer = min(answer)
print(f'{answer[1]} {answer[2]}')

75 74