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

Не могу решить задачу
Автор yefiminho, история, 10 месяцев назад, По-русски

Всем привет! Пытаюсь решить эту задачу с тренировок

Пришел к выводу, что если 1 и N соседи, причём 1 находится левее N и все элементы перестановки упорядочены по убыванию от N до 1, то мы всегда сможем оставить только одно число, в любом другом случае — нет

Написал такое решение, но получаю WA на 5 тесте

Можете подсказать что не так и в каком направлении думать?

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

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Могу намекнуть на решение для начала, потому что идея простая, а вот реализовывать её надо аккуратно, иначе будет +10 попыток ( как у меня :) ). Попробуй рассмотреть, в каком случае у тебя будет съедена ягода весом 1, потом весом 2, и т. д. Начинать рассматривать съеденые ягоды надо обязательно с самой маленькой из имеющихся, потому что она обязательно должна быть съедена одним из своих соседей, потому что если это не так, то она не может быть съедена ни одной из следующих ягод, потому что с каждой ягодной трапезой у тебя наименьший вес среди всех ягод может только возрастать. Как-то так. Готов ответить на вопросы по задаче дальше, если они у тебя появятся.

→ Ответить
  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Ягода с весом 1 может быть съедена только если одним из ее соседей является ягода с весом 2, соответственно ягода с весом 2 может быть съедена только если одним из её соседей является ягода с весом 3. Исходя из этого делаю так, нахожу позицию единички в массиве, ставлю два указателя l и r на ее соседей и запускаю цикл. Если левый сосед на единицу больше, то циклически сдвигаю l влево на одну позицию, рассматриваемый элемент тоже сдвигается влево, а r остается на месте. Если правый сосед на единицу больше, то циклически сдвигаю r на одну позицию вправо, рассматриваемый элемент сдвигается вправо, а l остается на месте. Если оба соседа не подходят, тогда выхожу из цикла. Цикл отрабатывает пока l != r. По выходу из цикла проверяю, что разница между рассматриваемым элементом и оставшимся соседом равна единице. Это решение тоже не проходит 5 тест. Идея же правильная?

    → Ответить
    • »
      »
      »
      10 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Идея правильная, попробуй для начала квадратичную реализацию. Пробегаешь по всему массиву находишь 1, смотришь есть ли у неё в соседях двойка, если есть удаляешь единичку. Потом смотришь на двойку и ищешь среди её соседей тройку, если находишь, то удаляешь уже двойку и т.д., пока у тебя в массиве не останется единственный элемент равный n, либо пока у тебя не получится найти соседа у некоторого элемента. Остается оптимизировать это решение. Дам небольшую подсказку, что квадратичную сложность можно уменьшить до линейной сложности с помощью указателей (не двух указателей, а указателей как типов данных в с++).

      → Ответить