Два указателя задача

Question

solve c++
A. Отрезок с небольшой суммой
ограничение по времени на тест1 секунда
ограничение по памяти на тест1024 мегабайта
Дан массив из n
чисел ai
. Скажем, что отрезок этого массива a[l..r]
(1≤l≤r≤n
) хороший, если сумма чисел на этом отрезке не больше s
. Ваша задача — найти самый длинный хороший отрезок.

Входные данные
Первая строка содержит целые числа n
и s
(1≤n≤105
, 1≤s≤1018
). Вторая строка содержит числа ai
(1≤ai≤109
).

Выходные данные
Выведите одно число — длину самого большого хорошего отрезка. Если таких отрезков нет, выведите 0
.

Answer 1

Эта задача решается с помощью метода двух указателей (или скользящего окна), который эффективно находит наибольший подотрезок, сумма которого не превышает $s$ .

Алгоритм:

Используем два указателя: left (начало подотрезка) и right (конец подотрезка).
Двигаем right, добавляя элементы в текущую сумму.
Если сумма превышает $s$ , двигаем left, уменьшая сумму.
Следим за максимальной длиной хорошего отрезка.

Этот метод работает за O(n), что подходит для ограничения $n \leq 10^5$ .

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

cpp
#include <iostream>
#include <vector>

using namespace std;

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

    long long sum = 0, max_len = 0;
    int left = 0;

    for (int right = 0; right < n; right++) {
        sum += a[right];

        while (sum > s && left <= right) {
            sum -= a[left];
            left++;
        }

        max_len = max(max_len, right - left + 1);
    }

    cout << max_len << endl;
    return 0;
}

Разбор кода:

Читаем входные данные.
Перебираем массив a с right:
- Добавляем a[right] в текущую сумму.
- Если сумма превышает s, сдвигаем left и уменьшаем сумму.
- Обновляем максимальную длину подходящего отрезка.
Выводим максимальную длину.

Сложность алгоритма:

Каждое число обрабатывается не более двух раз (right движется вперёд, left тоже), значит O(n).

Примеры работы:

Вход 1:

text
5 10
1 2 3 4 5

Выход 1:

(Самый длинный подотрезок: [1, 2, 3, 4], сумма = 10)

Вход 2:

text
3 5
10 20 30

Выход 2:

(Нет отрезков с суммой ≤ 5)

Этот алгоритм эффективно решает задачу и подходит для больших входных данных.