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
简单题，直接贪心很容易想到，只不过很难直接上。 拿一个序列作为基准，求个逆序对就好了。 树状数组或者归并都可以。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e6+5; int n,m; queue<int>q[30]; typedef long long ll; ll ans; int val[N],t[N]; char a[N],b[N]; inline void add(int x,int y) { while (x<=n) { t[x]+=y; x+=x&-x; } } inline ll ask(int x) { ll ans=0; while (x>0) { ans+=t[x]; x-=x&-x; } return ans; } int main() { scanf("%d",&n); scanf("%s",a+1),scanf("%s",b+1); ll ans=0,t=1,w=0; fo(i,1,n)q[a[i]-'A'].push(i); fo(i,1,n) { val[i]=q[b[i]-'A'].front(); q[b[i]-'A'].pop(); } fo(i,1,n) { ans+=ask(n)-ask(val[i]); add(val[i],1); } printf("%lld\n",ans); }