Разбор задачи «Коридор проверки»

Идея задачи

Нам дано:

• n учеников;
• высота арки h;
• рост каждого ученика.

Каждый ученик занимает:

• 1, если его рост <= h;
• 2, если его рост > h.

Нужно найти суммарную ширину, необходимую для прохода всех учеников.

Ключевое наблюдение

На каждого ученика мы смотрим независимо от остальных.

Если ученик невысокий, он добавляет к ответу 1. Если высокий, он добавляет к ответу 2.

Значит, задача сводится к очень простому подсчёту:

• пройти по всем ростам;
• для каждого прибавить либо 1, либо 2.

Никакой сортировки, сложных структур данных или хитрых формул здесь не требуется.

Как получить ответ

Пусть ans — искомая суммарная ширина.

Изначально ans = 0.

Дальше для каждого роста a[i]:

• если a[i] > h, то ans += 2;
• иначе ans += 1.

После обработки всех учеников число ans и будет ответом.

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

Пусть:

n = 6, h = 5
росты: 7 6 8 9 10 5

Рассмотрим каждого ученика:

• 7 > 5, добавляем 2;
• 6 > 5, добавляем 2;
• 8 > 5, добавляем 2;
• 9 > 5, добавляем 2;
• 10 > 5, добавляем 2;
• 5 <= 5, добавляем 1.

Итого:

2 + 2 + 2 + 2 + 2 + 1 = 11

Ответ: 11.

Почему решение корректно

Докажем, что описанный алгоритм всегда даёт правильный ответ.

Каждый ученик проходит через коридор независимо от других и занимает строго определённую ширину:

• либо 1, если его рост не превышает h;
• либо 2, если рост больше h.

Следовательно, общая необходимая ширина равна сумме вкладов всех учеников.

Алгоритм как раз и делает это:

• для каждого ученика правильно определяет его вклад;
• прибавляет этот вклад к общему ответу.

Значит, после обработки всех n учеников полученная сумма в точности равна требуемой суммарной ширине.

Следовательно, алгоритм корректен.

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

Мы один раз проходим по массиву ростов.

По времени

O(n)

По памяти

Если считывать числа по одному, то:

O(1)

Если сначала сохранить все росты в массив, то:

O(n)

Оба варианта подходят, но для такой задачи удобно использовать и любой из них.

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

#include <iostream>
using namespace std;

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

    int ans = 0;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;

        if (a > h) {
            ans += 2;
        } else {
            ans += 1;
        }
    }

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

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

n, h = map(int, input().split())
heights = list(map(int, input().split()))

ans = 0
for x in heights:
    if x > h:
        ans += 2
    else:
        ans += 1

print(ans)

Возможная компактная запись

Эту задачу можно решить и короче.

Python

n, h = map(int, input().split())
heights = list(map(int, input().split()))

print(sum(2 if x > h else 1 for x in heights))

C++

Хотя и в C++ можно писать короче, для обучения лучше оставить явный цикл — он проще и понятнее начинающим.

Частые ошибки

1. Перепутать знак сравнения

Нужно проверять именно:

a > h

Если рост равен h, ученик всё ещё проходит нормально и добавляет 1, а не 2.

2. Забыть, что ответ — это сумма по всем ученикам

Иногда по невнимательности считают только количество высоких учеников. Но нужно учитывать и тех, кто добавляет по 1.

3. Неправильно считать ввод

Во второй строке дано n чисел. Их нужно корректно обработать все.

Чему учит эта задача

Хотя задача очень простая, она полезна для тренировки базовых навыков:

• чтение входных данных;
• проход по массиву;
• работа с условиями if;
• аккуратный подсчёт ответа.

Это хороший пример задачи, где важно увидеть прямую модель:

вклад каждого элемента считается отдельно, а итоговый ответ — это сумма этих вкладов.

Такой подход встречается очень часто и в более сложных задачах.

Итог

Чтобы решить задачу, достаточно для каждого ученика:

• прибавить 1, если a[i] <= h;
• прибавить 2, если a[i] > h.

После этого вывести сумму.

Это даёт простое и эффективное решение за O(n).