TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4223
  • Problem
  • P4223彩色方块
    Limits : Time Limit : - MS   Memory Limit : 131072 KB
    Judgment Tips : 单个测试点1000ms
    Description

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

    Input Format

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

    Output Format

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

    Sample Input 1

    3
    RGB
    GBR

    Sample Output 1

    2

    Sample Input 2

    4
    AACB
    BACA

    Sample Output 2

    4

    Sample Input 3

    7
    ZZZAAAA
    ZAAZAAZ

    Sample Output 3

    6

    Hint

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

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


    Source  改编自Poi2012 Letters