Question

ДАЮ 100 БАЛЛОВ.Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы). Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа. Входные данныеВходной файла содержит количество чисел n, за которым следуют n целых чисел ai в порядке их добавления в набор. 1 ≤ n ≤ 106, −109≤ai≤109.Выходные данныеВыходной файл должен содержать n целых чисел — значения центрального элемента после каждого добавления.Примеры тестоввходные данные35 3 4выходные данные5 3 4входные данные51 2 3 2 4выходные данные1 1 2 2 2

Answer 1

Ответ:

with open('input.txt', 'r') as inp:

   k = int(inp.readline())

   a = [int(i) for i in inp.readline().split()]

middle_num = []

a_0 = []

for i in range(k):

   a_0.append(a[i])

   a_0.sort()

   m = int(len(a_0) / 2)

   middle = a_0[m]

   middle_num.append(middle)

with open('output.txt', 'w') as out:

   for element in middle_num:

       out.write(str(element))

       out.write(' ')

Объяснение:

язык питон 2.7 решение не полное, но мош защитала

Answer 2

Для решения этой задачи можно использовать структуру данных "куча" (heap) для эффективного нахождения медианы (центрального элемента) на каждом шаге добавления нового числа в набор. Куча позволяет быстро извлекать минимальный или максимальный элемент из набора.

В Python можно воспользоваться модулем `heapq`, который предоставляет функции для работы с кучей.

Пример кода:

import heapq

def find_median_after_adding_numbers(n, numbers):
    min_heap = []  # мин-куча для правой части набора
    max_heap = []  # макс-куча для левой части набора

medians = []

for i in range(n):
        num = numbers[i]

# Добавляем число в соответствующую кучу
        if not max_heap or num <= -max_heap[0]:
            heapq.heappush(max_heap, -num)
        else:
            heapq.heappush(min_heap, num)

# Балансируем кучи, чтобы разница в их размерах была не более 1
        while len(max_heap) > len(min_heap) + 1:
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        while len(min_heap) > len(max_heap):
            heapq.heappush(max_heap, -heapq.heappop(min_heap))

# Находим медиану и добавляем её в результат
        if i % 2 == 0:
            medians.append(-max_heap[0])
        else:
            medians.append((-max_heap[0] + min_heap[0]) / 2)

return medians

# Пример использования
n = 3
numbers = [3, 4]

result = find_median_after_adding_numbers(n, numbers)
print(result)

В этом примере используется две кучи: одна для хранения элементов слева от медианы (макс-куча), другая для элементов справа от медианы (мин-куча). Балансировка куч происходит так, чтобы разница в их размерах была не более 1. Это позволяет эффективно находить медиану на каждом шаге добавления нового числа.