Блог

Недавно я столкнулся с вопросом о кодировании в конкурсе, и я не могу найти способ решить эту проблему. (Я выхожу из конкурса :))

Итак, вот вопрос: рассмотрим массив целых чисел, где каждый элемент может быть изменен двумя операциями. Либо разделите элемент на 2, либо умножьте элемент на 2.

Учитывая k шансов изменить элементы массива с помощью вышеупомянутых операций (каждый раз, когда элемент изменяется, рассматривается как одна операция), найдите смежный подмассив максимальной длины, чтобы все элементы в подмассиве имели одинаковую четность.

Четность — остаток при делении числа на 2

например: — рассмотрим массив 12,11,10,4 и k = 1, здесь четность элементов равна 0,1,0,0. При умножении 2-го элемента 11 на 2 (и, следовательно, выполнении одной операции) мы можем получить четность 0 (поскольку 22 оставляет остаток 0) и, следовательно, учитывая k = 1 операций, максимальная длина непрерывного подмассива с элементами, имеющими одинаковую четность, равна 4

Это проще всего, если вы разделите его на две подзадачи: найдите самый длинный достижимый подмассив с четностью 0 с <= k ходов и найдите самый длинный достижимый подмассив с четностью 1 с <= k ходов. Затем выберите тот ответ, который длиннее.

Обе эти подзадачи легко решаются с помощью метода двух указателей. Для четности 0:

1. Назначьте младший и старший указатели на начало массива
2. Мы будем отслеживать, сколько ходов требуется для достижения четности 0 для подмассива между указателями. Инициализируйте стоимость этого подмассива равной 0.
3. Увеличьте верхний указатель. Добавьте стоимость для нового элемента в подмассиве.
4. Пока стоимость> k, увеличьте младший указатель и удалите стоимость элемента, который удаляется из подмассива.
5. Вернитесь к 3, пока старший указатель не выйдет из массива. Запомните самый длинный подмассив, который был виден на этом шаге.

Обратите внимание, что получение от 0 до четности 1 имеет бесконечную стоимость. Для целей приведенного выше алгоритма вы можете сказать, что это стоит k 1.