2789: [Poi2012]Letters
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 278 Solved: 185
[Submit][Status][Discuss]
Description
给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。
现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。
Input
第一行一个正整数n (2<=n<=1,000,000)，表示字符串的长度。
第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。
Output
一个非负整数，表示最少的交换次数。
Sample Input
3
ABC
BCA
ABC
BCA
Sample Output
2
HINT
ABC -> BAC -> BCA
Source
题解：
树状数组＋逆序对
口胡 ：Bzoj好像挂了QAQ，好伤心555555
好了，开始说正题。
首先，最少次数交换相邻的元素之类的肯定用树状数组求逆序对。然后考虑贪心。
这道题的贪心思路很好想，就是把B数列每个数把其在A数列中最近的数移过来。
例如：
A数列 : ABACA
B数列 : ABCAA
对于B数列中每个数，我们去找在A数列中应该出现的位置，若字母相同就往后找，直到找到第一个没有在A数列中选过的位置。
则上述例子可以得到数列：1 2 4 3 5
然后逆序对胡搞。。。
具体看程序，自己手推一下就懂了 ^w^
PS:把int变量定到char类型中也是爽。。。QAQ
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define MAXN 1000010
struct node
{
int v,w;
}a[MAXN],b[MAXN];
/*struct NODE
{
int v,w;
}b[MAXN];*/
int n;
int BIT[MAXN],c[MAXN];
char A[MAXN],B[MAXN];
bool cmp(node aa,node bb)
{
if(aa.v==bb.v)return aa.w<bb.w;
return aa.v<bb.v;
}
/*bool cmp1(NODE aa,NODE bb)
{
if(aa.v==bb.v)return aa.w<bb.w;
return aa.v<bb.v;
}*/
int Lowbit(int o){return o&(-o);}
void Update(int o,int o1)
{
while(o<=n)
{
BIT[o]+=o1;
o+=Lowbit(o);
}
}
int Sum(int o)
{
int sum=;
while(o>)
{
sum+=BIT[o];
o-=Lowbit(o);
}
return sum;
}
int main()
{
int i;
LL ans=;
scanf("%d",&n);
scanf("\n%s\n%s",A+,B+);
for(i=;i<=n;i++)
{
a[i].v=A[i]-'A'+;b[i].v=B[i]-'A'+;
a[i].w=b[i].w=i;
}
sort(a+,a+n+,cmp);
sort(b+,b+n+,cmp);
for(i=;i<=n;i++)c[a[i].w]=b[i].w;
memset(BIT,,sizeof(BIT));ans=;
for(i=n;i>=;i--)
{
ans+=Sum(c[i]-);
Update(c[i],);
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return ;
}