| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
Всем привет! Пытаюсь решить эту задачу с тренировок
Пришел к выводу, что если 1 и N соседи, причём 1 находится левее N и все элементы перестановки упорядочены по убыванию от N до 1, то мы всегда сможем оставить только одно число, в любом другом случае — нет
Написал такое решение, но получаю WA на 5 тесте
Можете подсказать что не так и в каком направлении думать?
Могу намекнуть на решение для начала, потому что идея простая, а вот реализовывать её надо аккуратно, иначе будет +10 попыток ( как у меня :) ). Попробуй рассмотреть, в каком случае у тебя будет съедена ягода весом 1, потом весом 2, и т. д. Начинать рассматривать съеденые ягоды надо обязательно с самой маленькой из имеющихся, потому что она обязательно должна быть съедена одним из своих соседей, потому что если это не так, то она не может быть съедена ни одной из следующих ягод, потому что с каждой ягодной трапезой у тебя наименьший вес среди всех ягод может только возрастать. Как-то так. Готов ответить на вопросы по задаче дальше, если они у тебя появятся.
Ягода с весом 1 может быть съедена только если одним из ее соседей является ягода с весом 2, соответственно ягода с весом 2 может быть съедена только если одним из её соседей является ягода с весом 3. Исходя из этого делаю так, нахожу позицию единички в массиве, ставлю два указателя l и r на ее соседей и запускаю цикл. Если левый сосед на единицу больше, то циклически сдвигаю l влево на одну позицию, рассматриваемый элемент тоже сдвигается влево, а r остается на месте. Если правый сосед на единицу больше, то циклически сдвигаю r на одну позицию вправо, рассматриваемый элемент сдвигается вправо, а l остается на месте. Если оба соседа не подходят, тогда выхожу из цикла. Цикл отрабатывает пока l != r. По выходу из цикла проверяю, что разница между рассматриваемым элементом и оставшимся соседом равна единице. Это решение тоже не проходит 5 тест. Идея же правильная?