Разбор задачи «Переполненный шаттл»

Идея задачи

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

Ключевое наблюдение очень простое:

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

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

Как моделировать процесс

Пусть:

• cur — текущее число пассажиров в шаттле;
• ans — максимальное число пассажиров, которое встретилось по ходу маршрута.

Изначально шаттл пуст, значит:

• cur = 0
• ans = 0

Для каждой остановки выполняем действия ровно в том порядке, который дан в условии:

1. из шаттла выходят a[i] пассажиров;
2. в шаттл заходят b[i] пассажиров;
3. обновляем максимум.

То есть формулы такие:

• cur -= a[i]
• cur += b[i]
• ans = max(ans, cur)

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

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

Докажем, почему достаточно взять максимум числа пассажиров по ходу движения.

Рассмотрим любое состояние шаттла после очередной остановки. В этот момент внутри находится cur пассажиров. Если вместимость меньше cur, то все пассажиры уже не поместятся. Значит, вместимость обязательно должна быть не меньше количества пассажиров в каждый момент времени.

Следовательно, она должна быть не меньше максимального из этих значений.

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

Итак:

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

Значит, этот максимум и есть минимальный возможный ответ.

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

Пусть входные данные такие:

4
0 3
2 5
4 2
4 0

Идём по остановкам.

Остановка 1

• вышло 0
• зашло 3
• стало 3

ans = 3

Остановка 2

• было 3
• вышло 2, осталось 1
• зашло 5, стало 6

ans = 6

Остановка 3

• было 6
• вышло 4, осталось 2
• зашло 2, стало 4

ans = 6

Остановка 4

• было 4
• вышло 4, осталось 0
• зашло 0, стало 0

ans = 6

Ответ: 6.

Алгоритм

1. Считать число остановок n.
2. Завести переменные cur = 0 и ans = 0.

3. Для каждой остановки:

   • считать a и b;
   • выполнить cur -= a;
   • выполнить cur += b;
   • обновить ans.
4. Вывести ans.

Сложность

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

• Время: O(n)
• Память: O(1)

Это оптимально для данной задачи.

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

1. Обновлять максимум не после всей остановки

Важно помнить: по условию сначала пассажиры выходят, потом заходят. Значит, нас интересует количество пассажиров после завершения остановки.

Правильно:

cur -= a;
cur += b;
ans = max(ans, cur);

2. Пытаться считать сумму всех вошедших

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

3. Перепутать порядок действий

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

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

#include <iostream>
using namespace std;

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

    int cur = 0;
    int ans = 0;

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

        cur -= a;
        cur += b;

        if (cur > ans) {
            ans = cur;
        }
    }

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

Пояснение к коду на C++

• cur хранит текущее количество пассажиров;
• ans хранит максимум;
• в цикле читаем одну остановку за другой и обновляем состояние шаттла.

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

n = int(input())

cur = 0
ans = 0

for _ in range(n):
    a, b = map(int, input().split())
    cur -= a
    cur += b
    if cur > ans:
        ans = cur

print(ans)

Пояснение к коду на Python

Логика полностью такая же, как и в реализации на C++:

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