TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4230
  • 题目
  • P4230方块消除
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    何老板最近在玩一款叫“方块消除”的手机游戏,游戏虽然简单,但何老板仍旧乐此不疲。
    游戏一开始有2*n个方块叠成一摞,每个方块都有一个编号,编号1到n。每个编号的都有两个方块。
    每次操作,玩家可以交换相邻两个方块。如果在交换操作后,两个相邻的方块编号相同,它们会消失,所有叠在它们上面的方块会落下来,并且可能由此产生连锁反应。
    何老板想知道,最少几次操作就能使得所有方块都消除掉。
    例1:如下图所示,只需在P1,P2处进行两次交换操作就可消除所有方块。

    例2:如下图所示的三次操作就可消除所有方块。

    输入格式

    第一行,一个正整数n(1<=n<=50000)。
    接下来2n行每行一个数,从上到下描述每个方块的编号
    游戏开始时,没有两个相同编号的方块相邻。
    保证所有关卡都能在1000000步以内消除掉。

    输出格式

    一行,一个整数,表示最少的所需操作步数。

    样例输入 1

    5
    5
    2
    3
    1
    4
    1
    4
    3
    5
    2

    样例输出 1

    2

    样例输入 2

    3
    1
    2
    3
    1
    2
    3

    样例输出 2

    3

    提示

    对于30%的数据:1<=n<=1000
    对于100%的数据:1<=n<=50000


    来源  改编自POI2007