6482: 积木游戏

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

n个小木块排成一排,每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种(约定:0表示红色,1表示黄色,2表示蓝色)。游戏开始时,要求通过翻着与交换方式对小木块重新排列(翻看的规则为每个小木块只能看一次),最终使相同颜色的木块排列在一起,如下图所示


设计一个翻看与交换的方案,实现上面的要求。例如,设中间状态如下:


此时,从A处开始进行翻看交换:

A为红色,则不用交换;

A为蓝色,交换一次,即AB交换;

A为黄色,交换两次,即AB交换一次,然后BC再交换一次继续翻看交换下一个积木直到完成排列,游戏结束。另外,初始状态A为第一块积木,BC为均最后一块积木。

输入格式

第一行为一个正整数n,表示积木的数量。
第二行为n个空格隔开的非负整数,表示初始积木的排列顺序,其中0表示红色,1表示黄色,2表示蓝色。

输出格式

一行一个整数,表示交换的次数。注意,如果按照上述规则交换时两个积木的位置重合,那么不需要计入总交换次数。

输入样例 复制

10
0 0 1 2 2 0 1 0 0 0

输出样例 复制

4

分类标签