TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5617
  • 题目
  • P5617黑白球
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    何老板将2N个小球排成一排。其中有N个白球和N个黑球。
    白球编号1到N,每个白球上都有一个数字,表示它的编号。
    黑球编号1到N,每个黑球上都有一个数字,表示它的编号。
    可以任意交换两个相邻小球,何老板想知道,最少几次交换就能满足下列要求:
    对于任意的(i,j), 1 ≤ i < j ≤ N,编号i的白球一定在编号j的白球左侧
    对于任意的(i,j), 1 ≤ i < j ≤ N,编号i的黑球一定在编号j的黑球左侧

    简单的说,最少进行几次交换,就能使得编号小的白球一定出现在编号大的白球的左侧,编号小的黑球一定出现在编号大的黑球的左侧。

    输入格式

    第一行,一个整数N
    接下来2N行,每行一个字母和一个整数,从左往右描述初始时每个小球的情况。
    字母‘W’表示该小球是白色,字母‘B’表示该小球是黑色。数字表示该小球的编号。

    输出格式

    一个整数,表示最少交换次数

    样例输入 1

    3
    B 1
    W 2
    B 3
    W 1
    W 3
    B 2

    样例输出 1

    4

    样例说明:
    交换黑3和白1
    交换白2和白1
    交换黑3和白3
    交换黑3和黑2

    样例输入 2

    4
    B 4
    W 4
    B 3
    W 3
    B 2
    W 2
    B 1
    W 1

    样例输出 2

    18

    样例输入 3

    9
    W 3
    B 1
    B 4
    W 1
    B 5
    W 9
    W 2
    B 6
    W 5
    B 3
    W 8
    B 9
    W 7
    B 2
    B 8
    W 4
    W 6
    B 7

    样例输出 3

    41

    提示

    $1 ≤ N ≤ 2000$


    来源  arc097E Sorted and Sorted