Popov AcademyУсловие
В списке из голосов некоторый вариант встречается строго больше раз; существование такого большинства гарантировано. Разрешено удалять из списка любые два голоса за разные варианты. Докажите, что, повторяя удаление до тех пор, пока оно возможно, вы определите исходное большинство. Как осуществить эту идею одним проходом, храня только один вариант-кандидат и счётчик?
О задаче · Подростки и взрослые
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Подсказка 1
При удалении двух разных голосов большинство теряет не больше одного голоса.
Подсказка 2
Когда счётчик равен нулю, следующий голос может стать новым кандидатом.
Разобрать решение по шагам
Докажите сохранение большинства
Пусть сейчас всего голосов, из них за исходный вариант большинства, и . После удаления разных голосов остаётся голоса. Голосов большинства остаётся не меньше , а
Если пара вообще не содержала большинства, его преимущество ещё сильнее. Значит, тот же вариант остаётся строгим большинством после каждого удаления.
Определите результат сокращения
Когда разные пары удалить уже нельзя, все оставшиеся голоса одинаковы. Пустой список получиться не может: на каждом шаге сохранялось строгое большинство. Следовательно, оставшийся вариант — именно исходное большинство, независимо от порядка удалений.
Замените список счётчиком
Идём слева направо. При нулевом счётчике запоминаем текущий голос как кандидата и ставим счётчик . Если следующий голос совпадает с кандидатом, увеличиваем счётчик; если нет, уменьшаем. Уменьшение мысленно удаляет текущий голос и один сохранённый голос кандидата. Счётчик описывает число ещё не спаренных одинаковых голосов. Поэтому итоговый кандидат совпадает с результатом допустимых удалений и является большинством.
Ответ
Удалять пары разных значений. Оставшийся кандидат — гарантированное большинство; потоковую реализацию даёт один кандидат со счётчиком.
Главная идея
Алгоритм можно обосновать, представив его действия как простые преобразования, сохраняющие искомое свойство.
Как заметить эту идею в другой задаче
Гарантирован строгий перевес одного значения. Удаление пары разных значений не уничтожает этот перевес; счётчик хранит непогашенную часть кандидата.
Возможная ошибка
Считать положительный итоговый счётчик доказательством большинства, если условие не гарантирует его существования.
Источник и примечания
Источник и редакция
Авторская учебная задача на классическую идею. Формулировка и разбор — Popov Academy.
Проверь себя
Гарантии большинства больше нет. Для списка , , алгоритм оставляет . Как проверить, действительно ли итоговый кандидат — большинство?
Ответ к дополнительной задаче
Сделать второй проход и посчитать его настоящие вхождения, сравнив с . В примере встречается один раз из трёх, поэтому большинства нет. Первый проход предлагает кандидата, а без исходной гарантии не подтверждает победу.
Тема, знания и приёмы
Поиск и алгоритмы · Нужна школьная база
- Код писать не нужно. Понадобятся точный план и проверка всех возможных случаев.
Приёмы решения: Инвариант или монотонная величина