Что спрашивают

Из N измерений удаляют N // 10 наименьших и N // 5 наибольших. Оба количества считают от исходного N; одинаковые значения остаются отдельными измерениями.

Найдите максимум среди оставшихся и целую часть их среднего. N ≤ 100 000, показания от 1 до 10^9; сумма может превышать 2^31.

Приём решения

Отсортируйте показания по возрастанию. Пусть left = N // 10, right = N - N // 5. Тогда нужная часть — срез values[left:right]. Правая граница среза не входит в него.

Поскольку удаляется не больше 30% исходных данных, хотя бы один элемент остаётся. Максимум оставшихся — последний элемент среза. Целая часть среднего положительных чисел вычисляется как sum(middle) // len(middle) без float и без округления к ближайшему.

Особое внимание нулевому числу удаляемых: при N < 5 верхнее удаление равно нулю. Срез до N работает, а запись values[:-0] дала бы пустой список. Формула правой границы устраняет этот случай.

Повторы нельзя убирать с помощью set: каждый повтор участвует и в количестве отбрасываемых, и в сумме. Python int хранит нужные большие суммы точно. Время O(N log N), память O(N).

Разбор на примере

Ввод

13
30
2
8
4
16
19
6
24
10
14
20
12
22

Вывод

22 13
Разбор примера по шагам
ЭтапЧисло измеренийЗначения / результат
Исходные данные13Оба процента считаются от 13
Удаляем минимум13 // 10 = 12
Удаляем максимумы13 // 5 = 224 и 30
Остаток10Максимум 22; 131 // 10 = 13

При N = 13 удаляются одно наименьшее и два наибольших показания: 2, 24 и 30. Остаются 4, 6, 8, 10, 12, 14, 16, 19, 20, 22. Их максимум 22, сумма 131, количество 10. Целая часть среднего 13,1 равна 13.

Код на Python и C++

Срез может содержать одно показание. Никакого специального ответа не требуется: максимум и среднее тогда совпадают с этим показанием.

В C++ вместо среза — индексы left и right: сумма считается циклом от left до right - 1, максимум — values[right - 1]. Ловушки с values[:-0] в C++ нет.

import sys


def solve(values):
    values = sorted(values)
    n = len(values)
    middle = values[n // 10:n - n // 5]
    return middle[-1], sum(middle) // len(middle)


if __name__ == '__main__':
    n, *values = map(int, sys.stdin.buffer.read().split())
    print(*solve(values))
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> values(n);
    for (long long& value : values)
        cin >> value;
    sort(values.begin(), values.end());
    int left = n / 10, right = n - n / 5;
    long long sum = 0;
    for (int i = left; i < right; i++)
        sum += values[i];
    cout << values[right - 1] << ' ' << sum / (right - left) << endl;
}

Типичные ошибки

  • Пересчитать 20% после удаления 10%

    Оба количества определяются по исходному N. Последовательный пересчёт изменяет множество оставшихся.

  • Округлить среднее через round

    Требуется целая часть, а не ближайшее целое. Для положительных сумм используйте целочисленное деление.

  • Убрать одинаковые значения

    Повторы — самостоятельные измерения. Удаление повторов меняет N, срез и среднее.