Матч 309, Координатор соревнования (ContestCoordinator)

Дивизион 2, Уровень 1

Координатору необходимо определить качество проведенного соревнования. Для этого из списка баллов, набранных участниками, следует убрать k наибольших и k наименьших (k может равняться нулю), и найти среднее арифметическое оставшихся баллов, которое полагается равным качеству соревнования. Необходимо найти такое k, для которого качество соревнования наибольшее и вывести его значение.

Класс: ContestCoordinator

Метод: double bestAverage(vector<int> scores)

Ограничения: numbers содержит от 1 до 50 элементов, 1 £ numbers[i] £ 100.

Вход. Оценки участников соревнований, заданные в массиве numbers.

Выход. Наибольшее возможное значение качества соревнования.

Пример входа

scores

{1}

{1, 2, 3, 4}

{1,1,999,999,1000,1000}

{1,13,8,6,7,9}

Пример выхода

1.0

2.5

999.0

7.5

РЕШЕНИЕ

сортировка + перебор

Отсортируем числа в массиве. Переберем все возможные значения k от 0 до len / 2, где len – длина массива scores. Для каждого значения k найдем среднее арифметическое элементов массива scores[k], scores[k+1], …, scores[len-k]. Среди всех найденных средних арифметических находим наибольшее.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <numeric>

using namespace std;

class ContestCoordinator

{

public:

double bestAverage(vector<int> scores)

{

int k, len = scores.size();

double res = 0;

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

for(k = 0; 2 * k <= len; k++)

res = max(res,accumulate(scores.begin() + k,scores.end() - k,0.0) / (len - 2 * k));

return res;

}

};