1. Идея

Нужно посчитать, сколько элементов массива строго больше среднего арифметического всех элементов.

Среднее равно sum / n, где sum — сумма всех чисел.

Тогда для каждого a[i] надо проверить условие:

a[i] > sum / n

Но сравнивать с дробным числом неудобно и иногда опасно из-за ошибок округления. Поэтому лучше преобразовать неравенство:

a[i] * n > sum

Значит, задача решается так:

• за первый проход считаем сумму всех элементов;
• за второй проход считаем, для скольких элементов выполняется a[i] * n > sum.

Это и есть требуемые два прохода по данным.

2. Наблюдения

1. Среднее арифметическое может быть нецелым.

   Например, для массива 1 2 3 среднее равно 2. Тогда только число 3 больше среднего.

   А для массива 1 2 среднее равно 1.5, и только 2 больше среднего.

2. Деление можно не выполнять.

   Вместо проверки x > sum / n проверяем x * n > sum.

   Это точное целочисленное сравнение.

3. Сумма может быть большой.

   При n до 2 * 10^5 и a_i до 10^9 сумма может достигать по модулю примерно 2 * 10^14, поэтому в C++ нужен тип long long.

4. Отрицательные числа тоже обрабатываются правильно.

   Например, если массив -5 -2 -3, среднее равно -10 / 3, и сравнение x * n > sum работает без изменений.

3. Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. В первом проходе по массиву найти сумму sum.
4. Во втором проходе по массиву:
   • если a[i] * n > sum, увеличить ответ.
5. Вывести ответ.

4. Почему это работает

Обозначим среднее арифметическое всех элементов как avg = sum / n.

Нас интересуют элементы, для которых выполнено:

a[i] > avg

Подставим avg:

a[i] > sum / n

Так как n > 0, можно умножить обе части на n, не меняя знак неравенства:

a[i] * n > sum

Значит, элемент больше среднего тогда и только тогда, когда выполняется условие a[i] * n > sum.

Следовательно:

• первый проход правильно находит sum;
• второй проход правильно считает количество элементов, больших среднего.

Именно это число и требуется вывести.

5. Сложность

• Время: O(n), потому что массив просматривается два раза.
• Память: O(n), так как элементы сохраняются в массиве.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    long long sum = 0;

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

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] * (long long)n > sum) {
            count++;
        }
    }

    cout << count << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

s = 0
for x in a:
    s += x

count = 0
for x in a:
    if x * n > s:
        count += 1

print(count)