1. Идея

Нужно найти медиану массива нечётной длины.

По определению, медиана — это элемент, который будет стоять ровно посередине после сортировки массива по неубыванию. Значит, достаточно:

1. считать все зарплаты;
2. отсортировать их;
3. вывести элемент с индексом n / 2.

Так как n нечётно, середина определена однозначно.

2. Наблюдения

• После сортировки массива из n элементов индексы идут от 0 до n - 1.
• Если n нечётно, то серединный элемент имеет индекс n / 2 при целочисленном делении.
• Например:
  • при n = 1 медиана имеет индекс 0;
  • при n = 3 медиана имеет индекс 1;
  • при n = 5 медиана имеет индекс 2.

Пример:

[5, -2, 5]

После сортировки:

[-2, 5, 5]

Индекс середины: 3 / 2 = 1, значит медиана — 5.

3. Алгоритм

1. Считать число n.
2. Считать массив a из n чисел.
3. Отсортировать массив a.
4. Вывести a[n / 2].

4. Почему это работает

По условию медиана — это число, которое окажется ровно посередине после упорядочивания всех значений.

После сортировки:

• слева от элемента a[n / 2] находится ровно n / 2 элементов;
• справа от него тоже находится ровно n / 2 элементов, потому что n нечётно.

Значит, элемент a[n / 2] и есть медиана по определению.

5. Сложность

Основное время занимает сортировка.

• Время: O(n log n)
• Память:
  • O(n) на хранение массива

Это укладывается в ограничения при n <= 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    cout << a[n / 2] << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))
a.sort()
print(a[n // 2])