Разбор задачи «Баланс нагрузки в микроэнергосети»

Идея задачи

Нам дан массив целых чисел a[0..n-1], где каждое число показывает изменение энергии на очередном участке цепочки:

• положительное число — приток энергии;
• отрицательное число — расход или потери.

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

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

Формализация

Пусть:

• balance = a[0] + a[1] + ... + a[i] — сумма на текущем префиксе.

Тогда:

• если для некоторого i выполнено balance < 0, ответ сразу NO;
• если после просмотра всех элементов отрицательного баланса не возникло, ответ YES.

Это классическая задача на префиксные суммы и однопроходную проверку массива.

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

По условию сеть ломается не тогда, когда конечная сумма отрицательна, а тогда, когда отрицательной становится сумма в какой-то момент процесса.

Это очень важное различие.

Например, для массива:

5 -10 10

итоговая сумма равна 5, то есть она положительная. Но после первых двух элементов баланс равен:

5 + (-10) = -5

Значит, сбой уже произошёл, и ответ должен быть NO.

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

Пошаговый пример

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

3 -1 2 -2 1

Будем последовательно накапливать баланс:

1. balance = 0 + 3 = 3
2. balance = 3 + (-1) = 2
3. balance = 2 + 2 = 4
4. balance = 4 + (-2) = 2
5. balance = 2 + 1 = 3

На каждом шаге баланс неотрицателен, значит ответ:

YES

Теперь другой пример:

2 -5 3 1

Считаем:

1. balance = 0 + 2 = 2
2. balance = 2 + (-5) = -3

Баланс стал отрицательным уже на втором шаге, поэтому можно сразу завершить программу и вывести:

NO

Алгоритм

1. Считать n.
2. Инициализировать переменную balance = 0.
3. Для каждого элемента массива:
   • прибавить его к balance;
   • если balance < 0, вывести NO и завершить программу.
4. Если цикл завершился без проблем, вывести YES.

Почему алгоритм корректен

Докажем корректность.

Наблюдение

После обработки первых i + 1 элементов переменная balance равна сумме этого префикса.

Это верно, потому что:

• сначала balance = 0;
• на каждом шаге мы добавляем очередной элемент массива;
• значит, после i-го шага balance содержит сумму a[0] + a[1] + ... + a[i].

Если алгоритм вывел NO

Это произошло в момент, когда balance < 0.

Но balance — это сумма некоторого префикса массива. Следовательно, существует этап передачи, на котором накопленный баланс отрицателен. По условию это означает выброс, значит правильный ответ действительно NO.

Если алгоритм вывел YES

Это значит, что на каждом шаге цикла выполнялось balance >= 0.

Так как balance на каждом шаге равен сумме соответствующего префикса, ни один префикс не оказался отрицательным. Значит, система ни разу не вошла в аварийное состояние, и правильный ответ — YES.

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

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

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

• Время: O(n)
• Память: O(1), если обрабатывать числа по мере чтения

Даже при n = 10^5 такое решение работает очень быстро.

Важные замечания по реализации

1. Почему нужен тип long long / большие целые

По условию:

• n до 10^5;
• a[i] по модулю до 10^9.

Сумма может по модулю доходить до порядка 10^14, поэтому в C++ нужно использовать long long.

В Python это не проблема, потому что int там длинный автоматически.

2. Можно не хранить весь массив

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

Это делает решение ещё более экономным по памяти.

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long balance = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        balance += x;

        if (balance < 0) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

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

• balance хранит текущую префиксную сумму.
• Как только сумма стала отрицательной, дальше продолжать нет смысла: ответ уже однозначно NO.
• Если цикл завершился полностью, значит все префиксы были неотрицательны.

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

import sys


def main():
    input = sys.stdin.readline

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

    balance = 0

    for x in arr:
        balance += x
        if balance < 0:
            print("NO")
            return

    print("YES")


if __name__ == "__main__":
    main()

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

• Переменная balance работает точно так же, как и в версии на C++.
• При первом отрицательном префиксе сразу печатаем NO.
• Иначе в конце печатаем YES.

Можно ли сделать ещё лучше

С точки зрения асимптотики — нет.

Чтобы понять, не становится ли какой-то префикс отрицательным, в худшем случае нужно посмотреть все числа хотя бы один раз. Значит, O(n) по времени — оптимально.

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

Ошибка 1. Проверять только итоговую сумму

Неверный подход:

если сумма всех элементов >= 0, то YES

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

Ошибка 2. Использовать int в C++

Сумма может не поместиться в 32-битный тип.

Ошибка 3. Не завершать программу сразу после отрицательного баланса

Это не ошибка по корректности, но лишняя работа. Как только найден отрицательный префикс, ответ уже известен.

Минимальная математическая формулировка

Нужно проверить условие:

a[0] >= 0
 a[0] + a[1] >= 0
 a[0] + a[1] + a[2] >= 0
 ...
 a[0] + a[1] + ... + a[n-1] >= 0

Если все эти неравенства выполняются, ответ YES, иначе NO.