2789: [Poi2012]Letters
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 236 Solved: 160
[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
如果没有相同的字母那就是十分简单的逆序对。。然后考虑有相同字母的情况可以显然的发现目标串中第n次出现的字母对应当前串第n次出现的字母。。然后就变成傻逼题了。。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 1000010;
char s[N],ss[N];
ll val[N],ans,n;
queue <int> q[26];
ll lowbit(ll x){return x&-x;}
void Insert(ll pos){for (ll i=pos;i<=n;i+=lowbit(i)) val[i]++;}
ll Query(ll pos){
ll res = 0;
for (ll i=pos;i;i-=lowbit(i)) res+=val[i];
return res;
}
int main(){
scanf("%d",&n);scanf("%s",s+1);
for (ll i=1;i<=n;i++) q[s[i]-'A'].push(i);
scanf("%s",ss+1);
for (ll i=1;i<=n;i++){
ll x = q[ss[i]-'A'].front();q[ss[i]-'A'].pop();
Insert(n-x+1);ans+=Query(n-x);
}
printf("%lld",ans);
}
评论 (0)
