Question

Даю 50 баллов
Помогите с задачей по c++
Пусть задана последовательность из N целых неотрицательных чисел. Медианой такой последовательности в случае нечетного N называется элемент, который будет равноудален от концов последовательности, если ее отсортировать по возрастанию или убыванию (нетрудно сообразить, что этот элемент имеет номер (N+1)∕2 в отсортированной последовательности, если номера считать с единицы). В случае четного N медианой называется среднее арифметическое двух элементов, которые окажутся на местах N∕2 и (N∕2)+1
, если последовательность отсортировать. Однако исходная последовательность не обязана быть отсортированной. Напишите программу, которая по заданной входной последовательности вычисляет ее медиану.
Формат входных данных
С клавиатуры вводится количество элементов массива n
(0 < n < 100) — размер массива. В следующей строке вводятся n элементов массива через пробел (0≤a[i]<10000
).
Формат выходных данных
Необxодимо вывести одно число — медиану ряда чисел.

входные данные
5
1 2 3 4 5
выходные данные
3

Answer 1

Код

• #include <iostream>
• #include <vector>
• template <class T>
• T order_statistics (std::vector<T> a, unsigned n, unsigned k);
• int main() {
•    std::vector<int> seq;
•    int N, input;
•    std::cin >> N;
•    for (int q = 0; q < N; ++q) {
•        std::cin >> input;
•        seq.push_back(input);
•    }
•    double median;
•    unsigned int len = seq.size();
•    if (len % 2 == 1) {
•        median = order_statistics(seq, len, (len+1) / 2);
•    }
•    else {
•        median = (order_statistics(seq, len, (len+1) / 2) + order_statistics(seq, len, (len+1) / 2 + 1)) / 2.0;
•    }
•    std::cout << "Median of seq: " << median;
•    return 0;
• }
• template <class T>
• T order_statistics (std::vector<T> a, unsigned n, unsigned k)
• {
•    using std::swap;
•    for (unsigned l=1, r=n; ; )
•    {
•        if (r <= l+1)
•        {
•            if (r == l+1 && a[r] < a[l])
•                swap (a[l], a[r]);
•            return a[k];
•        }
•        unsigned mid = (l + r) >> 1;
•        swap (a[mid], a[l+1]);
•        if (a[l] > a[r])
•            swap (a[l], a[r]);
•        if (a[l+1] > a[r])
•            swap (a[l+1], a[r]);
•        if (a[l] > a[l+1])
•            swap (a[l], a[l+1]);
•        unsigned
•                i = l+1,
•                j = r;
•        const T
•                cur = a[l+1];
•        for (;;)
•        {
•            while (a[++i] < cur) ;
•            while (a[--j] > cur) ;
•            if (i > j)
•                break;
•            swap (a[i], a[j]);
•        }
•        a[l+1] = a[j];
•        a[j] = cur;
•        if (j >= k)
•            r = j-1;
•        if (j <= k)
•            l = i;
•    }
• }