题解 P5149 【会议座位】

· · 题解

P5149 题解

题目本质：求逆序对

因此我们可以很容易的把这道题分为两部分：

  1. 求顺序。
  2. 求逆序对。

找到了题目切入点就可以开始切了

第一部分，可以使用Hash、Trie、甚至Map。而我推荐Trie，因为好打、较快、无错。为了获得顺序，我们只需要将附加数组记录顺序即可，代码如下：

void insert(char s[], int k) {
  int u = 1;
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    int a = s[i] - 'a';
    if (!ch[u][a]) ch[u][a] = ++tot;
    u = ch[u][a];
  }
  cnt[u] = k;
  return;
}

void find(char s[], int k) {
  int u = 1;
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    int a = s[i] - 'a';
    u = ch[u][a];
  }
  finded[k] = cnt[u];
}

完成这一部分，我们很容易就得到了坐位顺序，那么我们只需要求逆序对即可：

void MergeSort(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  MergeSort(l, mid), MergeSort(mid + 1, r);
  int i = l, j = mid + 1, t = l;
  while (i <= mid && j <= r)
    if (finded[i] <= finded[j])
      b[t++] = finded[i++];
    else
      b[t++] = finded[j++], ans += mid - i + 1;
  while (i <= mid) b[t++] = finded[i++];
  while (j <= r) b[t++] = finded[j++];
  for (int k = l; k <= r; ++k) finded[k] = b[k];
}

什么这不是归并排序嘛？

没错！但我加了一句话，看看

else
      b[t++] = finded[j++], ans += mid - i + 1;

就是在这里，我们统计了每次排序不符合顺序的个数，因此就得到了逆序对个数。

现在我们已经完成了两个部分，结合即可了，上完整代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 5e5 + 5;
int ch[MAXN][26 * 2], cnt[MAXN];
int n, ans, tot = 1, finded[int(1e5 + 5)], b[int(1e5 + 5)];
char s[6];
void insert(char[], int);
void find(char[], int);
void MergeSort(int, int);

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    insert(s, i);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    find(s, i);
  }

  MergeSort(1, n);
  cout << ans;
}

void insert(char s[], int k) {
  int u = 1;
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    int a = s[i] - 'a';
    if (!ch[u][a]) ch[u][a] = ++tot;
    u = ch[u][a];
  }
  cnt[u] = k;
  return;
}

void find(char s[], int k) {
  int u = 1;
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    int a = s[i] - 'a';
    u = ch[u][a];
  }
  finded[k] = cnt[u];
}

void MergeSort(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  MergeSort(l, mid), MergeSort(mid + 1, r);
  int i = l, j = mid + 1, t = l;
  while (i <= mid && j <= r)
    if (finded[i] <= finded[j])
      b[t++] = finded[i++];
    else
      b[t++] = finded[j++], ans += mid - i + 1;
  while (i <= mid) b[t++] = finded[i++];
  while (j <= r) b[t++] = finded[j++];
  for (int k = l; k <= r; ++k) finded[k] = b[k];
}

后记：

于是，你拿去交了；于是，你发现WA了4个点：

你忘了，不开 long long 见祖宗，你知道了怎么做，于是AC了这道题。