Привет Codeforces! Изучаю метод двух указателей. Решаю 279B - Книги. Алгоритм понятен. Но когда доходит до реализации постоянно не учитываю какие-то случаи, криво как-то выходит. Подскажите что может быть не так в этом коде или скажите как лучше/правильнее писать метод двух указателей чтоб не было так криво(и кода много и учитывается не все)? 16825421









Попробуй двигать правую границу пока двигается и обновлять ответ. Если ты не можешь передвинуть правую границу, то двигай левую.
Здесь решение, в котором я использовал сумму на префиксах, но также можем просто поддерживать баланс.
#include <bits/stdc++.h> using namespace std; int main() { int n, t; cin >> n >> t; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int pos1 = 0, pos2 = 0, bal = 0, ans = 0; while (a[pos1] > t && pos1 < n) pos1++; if (pos1 == n) { cout << 0; return 0; } vector<int> preffsum(n); preffsum[0] = a[0]; for (int i = 1; i < n; i++) { preffsum[i] = preffsum[i - 1] + a[i]; } pos2 = pos1; bal = a[pos1]; while (pos2 < n && pos1 < n) { if (pos1 > 0) bal = preffsum[pos2] - preffsum[pos1 - 1]; else bal = preffsum[pos2]; pos2 = max(pos1, pos2); if (bal <= t) { ans = max(ans, pos2 - pos1 + 1); pos2++; continue; } pos1++; } cout << ans; }Удобно перебирать левую границу циклом, а правую передвигать при любой возможности. ИМХО
Чтобы программа работала правильно, нужно удалить строку
if (right == time.size()) right--;, и поменять местами строкиsum -= time.at(right);иif (right > 0) right--;rightуказывает на элемент, который ещё не выбран, поэтому для правильного пересчета суммы его нужно уменьшить перед тем, как менятьsum. Код