P4375. Out of Sorts G

发表于 分类于 阅读次数： Waline： 本文字数： 573 阅读时长 ≈ 2 分钟

考点

  • 排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, bit[maxn];

struct node {
  int val_, id_;
  bool operator<(node &x) {
    if (val_ != x.val_) return val_ < x.val_;
    return id_ < x.id_;
  }
} arr[maxn];

int lowbit(int x) { return x & -x; }

void add(int x, int v) {
  while (x <= n) {
    bit[x] += v;
    x += lowbit(x);
  }
}

int query(int x) {
  int res = 0;
  while (x > 0) {
    res += bit[x];
    x -= lowbit(x);
  }
  return res;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> arr[i].val_, arr[i].id_ = i;
  sort(arr + 1, arr + 1 + n);
  int ans = 1;
  for (int i = 1; i <= n; ++i) {
    add(arr[i].id_, 1);
    ans = max(ans, query(n) - query(i));
  }
  cout << ans;
  return 0;
}

思路

P4378的加强版，假设有下列数组。

值 65 64 63 62 61
下标 1 2 3 4 5

第一次冒泡排序（正常的冒泡排序）后，成功将元素65送到了它应去的地方，下标5的位置。

值 64 63 62 61 65
下标 1 2 3 4 5

第二次排序后，将元素61送到了下标1的位置

值 61 64 63 62 65
下标 1 2 3 4 5

可以发现规律，设当前下标为x，值为arr[x]：

第一次操作会将x的左侧，某个大于arr[x]的元素A换到x的右侧，且A到达正确下标位置；

第二次操作会将x的右侧，某个小于等于arr[x]的元素B换到x的左侧，且B到达正确下标位置。

每一轮的双向排序，对于x而言，就是维护了一次两边的平衡。

那么统计每个x左边（含自己）有多少个不平衡的下标即可，随后遍历x打擂台取最大值即为最终轮数。

当然，平衡是对称的，你也可以统计每个x右边（含自己）有多少个不平衡的下标。

举上面那个例子

值 65 64 63 62 61
当前下标 1 2 3 4 5
应处下标 5 4 3 2 1

由于平衡是对称的，这里设“不平衡”代表应处下标大于当前下标

（你也可以反过来，结果一样的）

65的左边不平衡数有{65}，数量为1

64的左边不平衡数有{65、64}，数量为2

63的左边不平衡数有{65、64}，数量为2

62和61没有左边不平衡数

那么最终结果就是取最大值，2轮