洛谷P3531 [POI2012]LIT-Letters

题目描述

Little Johnny has a very long surname.

Yet he is not the only such person in his milieu.

As it turns out, one of his friends from kindergarten, Mary, has a surname of the same length, though different from Johnny's.

Moreover, their surnames contain precisely the same number of letters of each kind - the same number of letters A, same of letters B, and so on.

Johnny and Mary took to one another and now often play together.

One of their favourite games is to gather a large number of small pieces of paper, write successive letters of Johnny's surname on them, and then shift them so that they obtain Mary's surname in the end.

Since Johnny loves puzzles, he has begun to wonder how many swaps of adjacent letters are necessary to turn his surname into Mary's. For a child his age, answering such question is a formidable task.

Therefore, soon he has asked you, the most skilled programmer in the kindergarten, to write a program that will help him.

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

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

输入输出格式

输入格式：

In the first line of the standard input there is a single integer n(2<=n<=1000000) denoting the length of Johnny's surname.

The second line contains Johnny's surname itself, i.e., contains its n successive letters (without spaces).

The third line contains Mary's surname in the same format: a string of n letters (with no spaces either).

Both strings consist only of capital (upper-case) letters of the English alphabet.

In tests worth 30% of points it additionally holds that n<=1000

输出格式：

Your program should print a single integer to the standard output: the minimum number of swaps of adjacent letters that transforms Johnny's surname into Mary's.

输入输出样例

输入样例#1：

3
ABC
BCA

输出样例#1： 

2

说明

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

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

我们可以先考虑一下小的数据范围

如果只有A B两个字母

那么只有两种情况

1. A B \nA B 对于这种情况我们是不用进行交换的
2. A B \nB A 这种情况只需交换一次即可

为了方便讨论，我们把 A B按照顺序标号为1 2

那么第二种情况就是

1 2

2 1 此时2在1前，且2比1大(这不是废话么。。)

那么我们不难就会想到：逆序对

如果不放心，可以自己验证几组数据，意会一下就很明确了

现在就有两个问题：

一.逆序对怎么求

1.暴力，绝对TLE

2.归并排序

3.树状数组

二.怎么维护出现的顺序

楼下的那位大佬是用的类似于邻接表的一个东西，蒟蒻表示看不懂，，，，

我们不难发现这个位置是满足先进先标顺序的

那么开26个队列来维护就好了23333

另外

不开long long见祖宗！！！

多年oi一场空！！！！！！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<deque>
 7 #include<queue>
 8 #define LL long long 
 9 #define lb(x)    ((x)&(-x))
10 using namespace std;
11 const int MAXN=40000001;
12 inline int read()
13 {
14     char c=getchar();int x=0,f=1;
15     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
17 }
18 int n;
19 queue<int>q[28];
20 int a[MAXN];
21 int tree[MAXN];
22 inline void Point_Add(int pos,int val)
23 {
24     while(pos<=n)
25     {
26         tree[pos]+=val;
27         pos+=lb(pos);
28     }
29 }
30 inline int Interval_Sum(int pos)
31 {
32     int ans=0;
33     while(pos)
34     {
35         ans+=tree[pos];
36         pos-=lb(pos);
37     }
38     return ans;
39 }
40 int main()
41 {
42     n=read();
43     for(int i=1;i<=n;i++)
44     {
45         char c=getchar();
46         q[c-'A'].push(i);
47     }
48     char c=getchar();// 可恶的换行符 
49     for(int i=1;i<=n;i++)
50     {
51         char c=getchar();
52         a[i]=q[c-'A'].front();
53         q[c-'A'].pop();
54     }
55     LL ans=0;
56     for(int i=1;i<=n;i++)
57     {
58         Point_Add(a[i],1);
59         ans+=i-Interval_Sum(a[i]);// 树状数组求逆序对，不懂的自行百度 
60     }
61     printf("%lld",ans);
62     return 0;
63 }