Решение задачи Разделение на классы с Codeforces

Без пояснения   Просмотров: 1026

Напомним, что медиана массива [a1,a2,…,a2k+1] из нечетного количества элементов определяется следующим образом: пусть [b1,b2,…,b2k+1] — числа массива в отсортированном порядке. Тогда медиана этого массива равна bk+1.

В классе 2n учеников, уровень навыков i-го ученика равен ai. Не гарантируется, что все уровни навыков учеников различны.

Уровень навыков класса будем считать равным медиане уровней навыков учеников класса.

Как директор школы, вы хотели бы разделить всех учеников на 2 класса так, чтобы в каждом классе было нечетное количество учеников (не делящееся на 2). Количества учеников в классах могут быть равными или различными, на ваш выбор. Каждый ученик должен попасть ровно в один класс. Среди таких разделений вы хотите выбрать то, в котором модуль разности между уровнями навыков классов минимален.

Какой минимальный модуль разности вы можете получить?

Код 

#include <bits/stdc++.h>

using namespace std;

int TN = 1;

void sol () {

    long long n;

    cin >> n;

    vector <long long> a (2 * n);

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

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

    cout << a[n] - a[n - 1] << '\n';

}

int main () {

    cin >> TN;

    for (int i = 0; i < TN; ++i) { sol () ; }

    return 0;

}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp