Bzoj 2789: [Poi2012]Letters 树状数组,逆序对-白红宇

Bzoj 2789: [Poi2012]Letters 树状数组,逆序对

阅读量：5753 次

发布时间：2019-06-18

本文共 1673 字，大约阅读时间需要 5 分钟。

2789: [Poi2012]Letters

Time Limit: 20 Sec Memory Limit: 128 MB

Submit: 278 Solved: 185

[][][]

Description

给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。

现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。

Input

第一行一个正整数n (2<=n<=1,000,000)，表示字符串的长度。

第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。

Output

一个非负整数，表示最少的交换次数。

Sample Input

ABC

BCA

Sample Output

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

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 #define LL long long 9 #define MAXN 100001010 struct node11 {12 int v,w;13 }a[MAXN],b[MAXN];14 /*struct NODE15 {16 int v,w;17 }b[MAXN];*/18 int n;19 int BIT[MAXN],c[MAXN];20 char A[MAXN],B[MAXN];21 bool cmp(node aa,node bb)22 {23 if(aa.v==bb.v)return aa.w
            
             0)44 {45 sum+=BIT[o];46 o-=Lowbit(o);47 }48 return sum;49 }50 int main()51 {52 int i;53 LL ans=0;54 scanf("%d",&n);55 scanf("\n%s\n%s",A+1,B+1);56 for(i=1;i<=n;i++)57 {58 a[i].v=A[i]-'A'+1;b[i].v=B[i]-'A'+1;59 a[i].w=b[i].w=i;60 }61 sort(a+1,a+n+1,cmp);62 sort(b+1,b+n+1,cmp);63 for(i=1;i<=n;i++)c[a[i].w]=b[i].w;64 memset(BIT,0,sizeof(BIT));ans=0;65 for(i=n;i>=1;i--)66 {67 ans+=Sum(c[i]-1);68 Update(c[i],1);69 }70 printf("%lld",ans);71 fclose(stdin);72 fclose(stdout);73 return 0;74 }