Разбор задачи «Кратчайший подотрезок с суммой не меньше S»

1. Идея

Так как все элементы неотрицательны, при расширении подотрезка вправо его сумма только растёт, а при сдвиге левой границы вправо — только убывает. Это свойство монотонности позволяет применить метод двух указателей (скользящее окно) и найти ответ за один проход.

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

Будем двигать правую границу r и поддерживать текущую сумму окна. Как только сумма стала не меньше S, пытаемся сдвинуть левую границу l вправо, укорачивая окно, пока сумма всё ещё >= S. В каждый такой момент обновляем минимальную длину.

3. Алгоритм

1. Завести l = 0, текущую сумму cur = 0, ответ best = +бесконечность.
2. Для каждого r от 0 до n-1: прибавить a[r] к cur; пока cur >= S, обновить best длиной r - l + 1 и вычесть a[l], сдвинув l.
3. Если best не обновлялся — вывести -1, иначе best.

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

Для каждой правой границы r внутренний цикл оставляет левую границу в самом правом положении, при котором сумма ещё >= S, то есть находит кратчайшее окно, заканчивающееся в r. Перебрав все r, мы рассмотрели кратчайшие окна с каждым правым концом, а значит нашли глобальный минимум. Указатель l только растёт, поэтому суммарно проходов O(n).

5. Сложность

Каждый из указателей проходит массив один раз, итого O(n) по времени и O(1) дополнительной памяти. Сумма и S могут быть большими, поэтому используем 64-битные числа.

Код на C++17

#include <iostream>
#include <vector>
using namespace std;

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

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

    long long cur = 0;
    int l = 0;
    int ans = n + 1;

    for (int r = 0; r < n; r++) {
        cur += a[r];
        while (l <= r && cur >= S) {
            int len = r - l + 1;
            if (len < ans) ans = len;
            cur -= a[l];
            l++;
        }
    }

    if (ans == n + 1) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}

Код на Python 3

import sys
data = sys.stdin.buffer.read().split()
n = int(data[0]); S = int(data[1])
a = list(map(int, data[2:2 + n]))

l = 0
cur = 0
best = n + 1
for r in range(n):
    cur += a[r]
    while cur >= S:
        best = min(best, r - l + 1)
        cur -= a[l]
        l += 1
print(best if best <= n else -1)