Задача повышенной сложности
На каждом острове в архипелаге Алгосы живёт какое-то количество людей или же остров необитаем (тогда на острове живёт 0 людей). Пусть на i-м острове численность населения составляет ai. Тимофей захотел найти медиану среди всех значений численности населения.
Определение: Медиана массива чисел a_i —– это такое число, что половина чисел из массива не больше него, а другая половина не меньше. В общем случае медиану массива можно найти, отсортировав числа и взяв среднее из них. Если количество чисел чётно, то возьмём в качестве медианы полусумму соседних средних чисел, (a[n/2] + a[n/2 + 1])/2.
У Тимофея уже есть отдельно данные по северной части архипелага и по южной, причём значения численности населения в каждой группе отсортированы по неубыванию.
Определите медианную численность населения по всем островам Алгосов.
Подсказка: Если n –— число островов в северной части архипелага, а m –— в южной, то ваше решение должно работать за O(log(n+m).
В первой строке записано натуральное число n, во второй —– натуральное число m. Они не превосходят 10 000.
Далее в строку через пробел записаны n целых неотрицательных чисел, каждое из которых не превосходит 10 000, –— значения численности населения в северной части Алгосов.
В последней строке через пробел записаны m целых неотрицательных чисел, каждое из которых не превосходит 10 000 –— значения численности населения в южной части Алгосов.
Значения в третьей и четвёртой строках упорядочены по неубыванию.
Нужно вывести одной число — найденную медиану.
|
2 1 1 3 2 |
2
|
|
2 2 1 2 3 4 |
2.5
|
|
8 10 0 0 0 1 3 3 5 10 4 4 5 7 7 7 8 9 9 10 |
5
|