首页 > 代码库 > BZOJ 2789 letters(树状数组)
BZOJ 2789 letters(树状数组)
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2789
【题目大意】
给出两个字符串,通过A字符串相邻之间字符的交换得到B字符串,
求最小的交换次数
【题解】
最小交换则对于同个字符来说前后顺序不变,我们得到B序列的字符在A序列中的位置,
顺序插入计算后缀和即可。
【代码】
#include <cstdio>#include <algorithm>#include <queue>using namespace std;typedef long long LL;const int N=1000010;int c[N],pos[N],n;queue<int> q[30];LL ans;char A[N],B[N];void add(int x,int val){while(x)c[x]+=val,x-=x&-x;}int query(int x){int res;while(x<=n)res+=c[x],x+=x&-x;return res;}int main(){ scanf("%d %s %s",&n,A+1,B+1); for(int i=1;i<=n;i++)q[A[i]-‘A‘].push(i); for(int i=1;i<=n;i++){ pos[i]=q[B[i]-‘A‘].front(); q[B[i]-‘A‘].pop(); }ans=0; for(int i=1;i<=n;i++){ ans+=query(pos[i]); add(pos[i],1); }printf("%lld\n",ans); return 0;}
BZOJ 2789 letters(树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。