Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom8月前

12/11
17:27
树状数组

[bzoj 2789] [Poi2012]Letters

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给出两个长度相同且由大写英文字母组成的字符串A、B,保证A和B中每种字母出现的次数相同。

现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个正整数n (2<=n<=1,000,000),表示字符串的长度。

第二行和第三行各一个长度为n的字符串,并且只包含大写英文字母。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个非负整数,表示最少的交换次数。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3
ABC
BCA

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

ABC -> BAC -> BCA

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

对于某个字母,它最后在B串中的排名应该和在A串中的是相同的,因为如果两个相同的字母交换的话很显然不必要,所以肯定是不优的,然后就可以得出A串中的每个位置在B串中的位置,最后求一遍逆序对数就行了

 

[bzoj 2789] [Poi2012]Letters