Блог пользователя moskalenco_a

Автор moskalenco_a, история, 9 лет назад, По-русски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Попробуй двигать правую границу пока двигается и обновлять ответ. Если ты не можешь передвинуть правую границу, то двигай левую.

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

код
»
9 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Удобно перебирать левую границу циклом, а правую передвигать при любой возможности. ИМХО

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Чтобы программа работала правильно, нужно удалить строку if (right == time.size()) right--;, и поменять местами строки sum -= time.at(right); и if (right > 0) right--;

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