题目
题目描述: 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2。
那么这个序列的逆序数为7,逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。
输入描述:
第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数,对于第i个数a[i],(0 <= a[i] <= 100000)。 输出描述:
输出这个序列中的逆序数。
解析
求逆序数,我相信大家学过线代的一定都很熟了,逆序数怎么算。
就是求每一个数前面有多少个比自己要大的数呗(或者后面有多少比自己小也行)。
知识点
这道题的知识点可以很多:线段树,树状数组,归并排序(因为我只会归并排序的,所以我们就归并吧)。
归并排序
- 我们就先简单的来讲一下,归并排序时怎么归的。
- 我们首先就是递归的,将一个数组分成左右两个部分。直到每个部分只剩下一个为止。
- 然后在从这无数个一个的数据再逐渐的合并,合并用什么呢?就用二路归并。
)别吐槽我字丑 - 二路归并咋整呢?其实就是两个有序的序列,用两个指针分别指着他们的头,然后比大小放进去就行了。
算法讲解
- 既然我们已经归并排序怎么归的了,那我们就要知道他怎么求逆序数了。
- 首先我们要知道归并是利用了什么求出来的逆序数:在二路归并的时候,如果序列后面的数跑到前面来了,中间路过了多少个数,他前面就有多少个数比他大。
这不就正好是,计算前面有多少个数比他大的过程吗嘿嘿。
- 所以我们就在二路归并的时候计数器累加一下就好了。
算法操作
- 我们已经知道是归并排序了,而且知道了原理,我就直接来讲一下怎么用吧。
- 首先是归并分块,将一个区间递归分块:
int mid = l + r >> 1; merge_sort(l, mid); merge_sort(mid + 1, r);
- 递归到区间长度为1为止:
if (l == r) return;
- 然后我们就可以进行二路归并了。
- 二路归并我们考虑从区间首位置(l)和区间中间(mid+1)开始,为两个区间,开始二路归并:
while (x <= mid && y <= r) { if (info[x] > info[y]) { tmp[pos++] = info[y++]; ans += mid - x + 1; } //如果前面的数大于后面的,说明我们在临时数组要保存后面的 //既然是要保存后面的,说明后面那个数要跳跃mid - x + 1个到前面来 else { tmp[pos++] = info[x++]; } }
为什么是mid - x + 1?因为每次往前跳就是跳第一段区间还剩下来的位置。为什么不加mid + 1到y的距离?因为前面的已经拿走了啊。 - 当其中一路判断完之后呢,我们就可以把另外一路剩下来的放进来了:
while (x <= mid) tmp[pos++] = info[x++]; while (y <= r) tmp[pos++] = info[y++];
- 最后吧这些放回原来的数组就好:
for (int i = r; i >= l; i--) info[i] = tmp[--pos];
打代码
- 首先是输入我们的数据。
- 接下来就按照我们上面说的操作进行归并排序。
- 然后看我完整代码吧~
AC代码
#include <iostream> using namespace std; typedef long long ll; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 1e5 + 7; int n, info[MAX], tmp[MAX]; ll ans; //全局变量区 void merge(int l, int mid, int r); void merge_sort(int l, int r); //函数预定义区 int main() { IOS; cin >> n; for (int i = 1; i <= n; i++) cin >> info[i]; merge_sort(1, n); cout << ans << endl; return 0; } void merge_sort(int l, int r) { if (l == r) return; int mid = l + r >> 1; merge_sort(l, mid); merge_sort(mid + 1, r); merge(l, mid, r); } void merge(int l, int mid, int r) { int x = l, y = mid + 1;//左右进行二路归并 int pos = 1;//记录临时数组的最大位置 while (x <= mid && y <= r) { if (info[x] > info[y]) { tmp[pos++] = info[y++]; ans += mid - x + 1; } //如果前面的数大于后面的,说明我们在临时数组要保存后面的 //既然是要保存后面的,说明后面那个数要跳跃mid - x + 1个到前面来 else { tmp[pos++] = info[x++]; } } while (x <= mid) tmp[pos++] = info[x++]; while (y <= r) tmp[pos++] = info[y++]; for (int i = r; i >= l; i--) info[i] = tmp[--pos]; } //函数区