题解 P5149 【会议座位】

Baihua · 2018-12-24 21:44:24 · 题解

思路 ：求逆序对个数

• 字符串可以用STL中提供的map解决。

• 成功把字符串转化成数字序列B后，就可以利用树状数组 或者归并排序 求逆序对了 。

• 关于树状数组求逆序对的原理：

  1. 对于任意的B[i] ，Add(B[i],1) 表示B[i] 已经出现过。
  3. 已经插入的i-1 个数字里，有i-1-Ask(B[i]-1) 个数大于B[i] ，它们和B[i] 构成了逆序对。
  4. 累加答案即可

• 点击这里学习树状数组

• Code

  #include <iostream>
  #include <fstream>
  #include <algorithm>
  #include <string.h>
  #include <stdio.h>
  #include <map>
  #define re register
  #define GC getchar()
  #define Lowbit(X) (X&(-X))
  using namespace std ;
  const int Maxn = 100000  , Dlt = 1;
  int N ;
  struct Person {
  int Place ;
  string Name ;
  };
  Person A[Maxn + Dlt] ;
  map <string , int > M ;
  int B[Maxn + Dlt] ;
  int T[Maxn + Dlt] ;
  /*
  头文件和准备工作
  结构体Person 中的Place是原有的位置，Name是对应的字符串；
  数组B是打乱的序列，T是树状数组。
  */
  void Add (int X , int K) {
  while (X <= N) {
      T[X] += K ;
      X += Lowbit(X) ;
  }
  }
  int Ask (int X) {
  int Ans = 0 ;
  while (X > 0) {
      Ans += T[X] ;
      X -= Lowbit(X) ;
  }
  return Ans ;
  }
  //树状数组的添加和查询操作
  int main () {
  //freopen ("P5149.in" , "r" , stdin) ;
  scanf ("%d" , &N) ;
  M.clear();
  for (re int i = 1 ; i <= N ; ++ i) {
      cin >> A[i].Name ;
      M[A[i].Name] = i ;
  }
  string S ;
  for (re int i = 1 ; i <= N ; ++ i) {
      cin >> S ;
      B[i] = M[S] ;
  }
  //    利用map完成把字符串转化为数字的操作，方便后续树状数组的操作
  memset (T , 0 , sizeof(T)) ;
  long long int Ans = 0 ;
  for (re int i = 1 ; i <= N ; ++ i) {
      Add (B[i] , 1) ;
      Ans += i - Ask(B[i] - 1) - 1 ;
  }
  cout << Ans<<endl;
  fclose (stdin) ;
  fclose (stdout);
  return 0;
  }

  Thanks!