Member 13664362 Ответов: 1

Минимальное количество свопов, которые должны быть сделаны в массиве таким образом, чтобы ни один из двух соседних элементов не был одинаковым.

Минимальное количество свопов, которые должны быть сделаны в массиве таким образом, чтобы ни один из двух соседних элементов не был одинаковым.

n = 6 а[] = {1, 1, 5, 2, 5, 5} Ответ = 1 ( Замените a[0] на a[4] или a[5] )

n = 8 а[] = {1, 5, 5, 1, 4, 6, 1, 1} Ответ = 2 (Замените a[0] на a[1] и a[5] на a[6] )
n = 8 а[] = {3, 1, 1, 5, 3, 3, 5, 5} Ответ = 2 (Замените a[0] на a[1] и a[5] на a[6] )
индексация с нуля в приведенных выше примерах.

Обратитесь за вопросом: Минимальное количество свопов, которые должны быть сделаны в массиве таким образом, чтобы ни один из двух соседних элементов не был одинаковым. - Codeforces[^]

Что я уже пробовал:

Логика 1: Подсчитайте общее число последовательных пар и вычтите его из числа оставшихся элементов. Но это, кажется, работает не во всех случаях.

1 Ответов

Рейтинг:
1

Patrice T

Это соревнование, поэтому по определению вы должны сами найти решение.
Поэтому, если мы дадим вам решение, это будет означать, что вы потерпели неудачу.

Цитата:
Логика 1: Подсчитайте общее число последовательных пар и вычтите его из числа оставшихся элементов. Но это, кажется, работает не во всех случаях.

Это означает, что вы должны усовершенствовать свой алгоритм.
Найдите примеры, которые не работают, и найдите, какие изменения нужно внести в ваш алгоритм.
Обратите внимание, что некоторые образцы не могут иметь никакого решения:
n = 4 a[] = {1, 1, 2, 1} answer = 0, no solution
n = 5 a[] = {1, 1, 2, 1, 2} answer = 2  (swap a[1] with a[2] and a[3] with a[4] )

[Обновление]
Цитата:
Я не могу решить этот вопрос, и в интернете нет большой помощи.

Попробуйте создать алгоритм brut force: попробуйте все возможные свопы и комбинации кратных свопов.

Member 13664362

Я не могу решить этот вопрос, и в интернете нет большой помощи.