在阵列中完成最小的交换次数，使得两个相邻的元素不相同。 [英] Minimum no of swaps to be done in an array such that, no two adjacent elements are same.

问题描述

在数组中完成最小数量的交换，使得两个相邻的元素不相同。



n = 6 a [] = {1,1， 5,2,5,5} answer = 1（用[4]或[5]交换a [0]）



n = 8 a [] = {1,5,5,1,4,6,1,1}回答= 2（用[1]交换a [0]，用[6]交换[5]）

n = 8 a [] = {3,1,1,5,3,3,5,5} answer = 2（用[1]交换a [0]，用[6]交换[5]） />
在上面的示例中从零开始索引。



参考问题：在数组中完成最小的交换次数，使得两个相邻的元素不相同。 - Codeforces [ ^ ]



我尝试过：



逻辑1：计算连续对的总数，并减去它来自剩余元素的数量。但它似乎并不适用于所有情况。

Minimum no of swaps to be done in an array such that, no two adjacent elements are same.

n = 6 a[] = {1, 1, 5, 2, 5, 5} answer = 1 ( swap a[0] with a[4] or a[5] )

n = 8 a[] = {1, 5, 5, 1, 4, 6, 1, 1} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )
n = 8 a[] = {3, 1, 1, 5, 3, 3, 5, 5} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )
indexing from zero in above examples.

Refer for question: Minimum no of swaps to be done in an array such that, no two adjacent elements are same. - Codeforces[^]

What I have tried:

Logic 1: count total number of consecutive pairs, and subtract it from the count of remainder elements. But it doesnt seem to work in all cases.

推荐答案

这是一场比赛，所以根据定义，你必须自己找到一个解决方案。

因此，如果我们给你一个解决方案，那就意味着你失败了。

This is a contest, so by definition, you have to find a solution yourself.
So if we give you a solution, it will mean that you failed.

引用：

逻辑1：计算连续对的总数，并从余数元素的数量中减去它。但它似乎并不适用于所有情况。

Logic 1: count total number of consecutive pairs, and subtract it from the count of remainder elements. But it doesnt seem to work in all cases.

这意味着你必须优化你的算法。

查找不起作用的样本并搜索对你的算法做什么改变。

请注意，有些样本没有解决方案：

That mean that you have to refine your algorithm.
Find samples that don't work and search what changes to do to your algorithm.
Note that some samples can have no solution:

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] )

[更新]

[Update]

引用：

我不能解决问题，并没有太多帮助在线。

Im not able to solve the question, and there is not much help online.

尝试设置一个强制算法：尝试每个可能的交换和多次交换的组合。

Try to device a brut force algorithm: try every possible swap and combinations of multiples swaps.

这篇关于在阵列中完成最小的交换次数，使得两个相邻的元素不相同。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！