TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4223
  • 题目
  • P4223彩色方块
    限制 : 时间限制 : - MS   空间限制 : 131072 KB
    评测说明 : 单个测试点1000ms
    问题描述

    何老板最近在玩一款叫“彩色方块”的小游戏,游戏虽然简单,但何老板仍旧乐此不疲。
    游戏中有n个彩色方块成一排,方块的颜色用字母表示,给出目标排列,只要把它们排成跟目标一样的排列,就算过关。每次操作只能交换相邻两个方块。
    给出一关游戏,何老板想知道,最少操作几次就能过关,请你帮他计算最少所需的操作步数。

    输入格式

    第一行,一个整数n表示方块的数量
    第二行,n个大写字母,表示一开始方块的排列情况。每个字母表示对应方块的颜色。
    第三行,n个大写字母,表示方块的目标排列情况。

    输出格式

    一行,一个整数,表示计算结果。
    数据保证有解。

    样例输入 1

    3
    RGB
    GBR

    样例输出 1

    2

    样例输入 2

    4
    AACB
    BACA

    样例输出 2

    4

    样例输入 3

    7
    ZZZAAAA
    ZAAZAAZ

    样例输出 3

    6

    提示

    样例1解释:
    RGB -> GRB -> GBR

    对于100%的数据:2<=n<=1,000,000


    来源  改编自Poi2012 Letters