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
题解
和noip2013《火柴排队》一样,排序搞搞逆序对即可。记得最终答案开long long。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define MAXN 1000005 #define ll long long using namespace std; int n; char A[MAXN],B[MAXN]; struct dian{int w,v;} a[MAXN],b[MAXN]; int tr[MAXN],num[MAXN]; bool kp(const dian &i,const dian &j) { if(i.v<j.v) return true; else if(i.v==j.v&&i.w<j.w) return true; else return false; } void init() { scanf("%d",&n); int i; scanf("%s%s",A+1,B+1); for(i=1;i<=n;i++) {a[i].v=A[i]-'A'+1; b[i].v=B[i]-'A'+1; a[i].w=i; b[i].w=i; } sort(a+1,a+n+1,kp); sort(b+1,b+n+1,kp); } int lowbit(int x){return x&(-x);} int find(int x) { int sum=0; for(;x<=n;x+=lowbit(x)) sum+=tr[x]; return sum; } void insert(int x) { for(;x>0;x-=lowbit(x)) tr[x]++; } void work() { int i; ll ans=0; for(i=1;i<=n;i++) num[a[i].w]=b[i].w; for(i=1;i<=n;i++) {ans+=find(num[i]+1); insert(num[i]); } printf("%lld\n",ans); } int main() { //freopen("letters.in","r",stdin); //freopen("letters.out","w",stdout); init(); work(); return 0; }