Решение задачи "Достигнуть медианы" с Codeforces

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


Вам дан массив a, состоящий из n чисел и число s. Гарантируется, что n является нечётным.

За одно действие вы можете понизить или повысить любой элемент на один. Вычислите минимальное количество действий, которое нужно проделать, чтобы сделать медиану массива равной s.

Медиана массива нечётной длины определяется как значение элемента, который будет расположен на центральной позиции после сортировки массива. Например, медиана массива 6,5,8 равна 6, потому что если мы отсортируем этот массив, то мы получим 5,6,8, и 6 расположена на центральной позиции.

Код

#include<bits/stdc++.h>
using namespace std;
int64_t n,s,i,r,a[200000];
int main(){
	for(cin >> n >> s; i < n; i++)
        cin >> a[i];
	sort(a , a + n);
	if(a[n / 2] < s){
		for(i = n / 2; i < n; i++)
            if(a[i] < s)
                r += s - a[i];
	}
	else{
		for(i = n/2; i >= 0; i--)
            if(a[i] > s)
                r += a[i] - s;
	}
	cout << r;
}

         

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


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

Комментарии

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