Разбор задачи «Фильтрация аномалий датчиков»

Идея задачи

Нам дан массив вещественных чисел — показания датчика. Нужно определить, сколько из них считаются аномальными.

По условию значение x является аномалией, если

|x - mean| > T

где:

• mean — среднее арифметическое всех элементов массива,
• T — допустимое отклонение.

Иначе говоря, сначала мы находим среднее значение всех измерений, а затем для каждого элемента проверяем, насколько сильно он от него отличается.

Что здесь требуется заметить

В задаче нет необходимости в сложных структурах данных, сортировках или хитрых оптимизациях.

Нужно сделать всего три шага:

1. Считать все числа.
2. Найти их среднее арифметическое.
3. Ещё раз пройти по массиву и посчитать, сколько элементов отличаются от среднего больше чем на T.

Это классическая задача на аккуратную реализацию.

Пошаговый алгоритм

Пусть массив называется a.

Шаг 1. Находим сумму

Складываем все элементы массива:

sum = a[0] + a[1] + ... + a[n-1]

Шаг 2. Находим среднее

Среднее арифметическое:

mean = sum / n

Шаг 3. Считаем аномалии

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

|a[i] - mean| > T

Если оно выполняется, увеличиваем ответ на 1.

Почему решение правильное

По условию задачи аномалией считается именно то значение, для которого модуль разности между этим значением и средним арифметическим всех измерений строго больше T.

Наш алгоритм:

1. точно вычисляет среднее арифметическое всех элементов массива;
2. для каждого элемента массива отдельно проверяет ровно это условие;
3. считает количество элементов, для которых условие истинно.

Значит, каждый элемент будет классифицирован правильно, и итоговое количество аномалий тоже будет найдено верно.

Оценка сложности

Мы дважды проходим по массиву:

• первый раз — чтобы найти сумму,
• второй раз — чтобы посчитать количество аномалий.

Итоговая сложность:

O(n)

По памяти:

O(n)

если мы храним массив целиком.

Заметим, что при желании задачу можно решить и с хранением массива, и без него. Но поскольку вход подаётся так, что после чтения массива ещё приходит T, удобнее сохранить элементы, а затем выполнить вторую проверку.

Важные замечания

1. Числа вещественные

Здесь элементы массива и число T — вещественные. Поэтому:

• в C++ лучше использовать double,
• в Python подойдёт float.

2. Сравнение строгое

В условии стоит именно знак >.

То есть если

|x - mean| = T

то это не аномалия.

3. Не нужно округлять среднее

Среднее нужно использовать как есть. Любое искусственное округление может испортить ответ.

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

Рассмотрим массив:

10 11 12 13 50

Сумма:

10 + 11 + 12 + 13 + 50 = 96

Среднее:

96 / 5 = 19.2

Пусть T = 5.

Тогда отклонения:

• |10 - 19.2| = 9.2
• |11 - 19.2| = 8.2
• |12 - 19.2| = 7.2
• |13 - 19.2| = 6.2
• |50 - 19.2| = 30.8

Все они строго больше 5, значит ответ равен:

5

Реализация на C++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

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

    double T;
    cin >> T;

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

    double mean = sum / n;

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (fabs(a[i] - mean) > T) {
            count++;
        }
    }

    cout << count;
    return 0;
}

Комментарий к коду

• vector<double> a(n) хранит все показания.
• sum используется для подсчёта суммы.
• mean = sum / n — среднее арифметическое.
• fabs(...) берёт модуль вещественного числа.
• В переменной count накапливается количество аномалий.

Реализация на Python

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

sum_values = 0.0
for x in a:
    sum_values += x

mean = sum_values / n

count = 0
for x in a:
    if abs(x - mean) > T:
        count += 1

print(count)

Комментарий к коду

• map(float, input().split()) считывает вещественные числа.
• sum_values хранит сумму всех элементов.
• mean — среднее значение.
• abs(x - mean) — модуль отклонения элемента от среднего.
• Если это отклонение больше T, увеличиваем ответ.

Почему здесь не нужны более сложные методы

Иногда в задачах на массивы хочется искать какой-то «умный» способ: сортировать, строить префиксные суммы, использовать бинарный поиск. Здесь всё это лишнее.

Причина проста: условие для каждого элемента проверяется независимо после того, как уже известно среднее. А среднее можно найти обычным проходом по массиву.

Поэтому самое лучшее решение здесь — прямое и линейное.