Abby有一套特殊的卡牌,他们是1-N数字的排列,每个数字有且仅有一张卡。 Abby在洗牌之后,会把卡牌并排放在地上。 Abby总是在通过卡牌的交换位置来获得1,2,3....N的序列。 假如初始序列是2、3、5、4、1,
我们就可以按照以下方式对它们进行排序:
初始状态:2 3 5 4 1
第一次后:1 3 5 4 2
第二次后:1 3 2 4 5
第三次后:1 2 3 4 5
所以,这里Abby对卡牌进行了三次交换。 那么我们的问题是,给定一个特定卡牌序列,Abby最少需要进行多少次互换才能达成她的目标。