满足a[I] > a[j], i < j称之为逆序对,给定一个整数N代表序列长度,第二行包含N个整数,代表序列中的元素,求出序列中逆序对的个数 例如:输入4 2 4 1 7 结果是2
时间: 2024-06-03 19:07:09 浏览: 12
解题思路:
一般求逆序对的方法有两种,一种是归并排序,一种是树状数组。这里介绍归并排序的方法。
归并排序的基本思想是分治,在归并排序的过程中,每次将序列二分,分别对左右两半进行排序,然后将左右两半合并成有序序列。在合并的过程中,统计逆序对的个数。
具体实现:
在合并两个有序序列时,假设左序列为A,右序列为B,分别从头开始遍历两个序列,对于A[i] > B[j] 的情况,表示存在逆序对,此时统计逆序对的个数为 mid - i + 1,其中 mid 为序列中间位置,i 为左序列当前位置。
C++代码:
相关问题
给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
题目描述
给定N个数的序列a1,a2,…,aN,定义一个数对(ai,aj)为“重要逆序对”的充要条件为i<j且ai>2aj。求给定序列中“重要逆序对”的个数。
输入格式
第一行一个整数N(1≤N≤105),表示序列中数的个数。
第二行N个整数a1,a2,…,aN(1≤ai≤109)。
输出格式
输出一个整数,表示给定序列中“重要逆序对”的个数。
样例
输入样例:
5
1 3 2 4 5
输出样例:
2
算法1
(归并排序) $O(nlogn)$
我们借鉴归并排序中的分治思路,假设当前要排序的区间为[l,r],可以将其拆分成两个区间:[l,mid]和[mid+1,r],排序后合并。
我们可以在合并时统计重要逆序对的数量。此时我们已经分别求出了[l,mid]和[mid+1,r]中的重要逆序对数量,因此[l,mid]和[mid+1,r]中分别分别排序后的数组已经是有序的。
接下来,在合并[l,mid]和[mid+1,r]的过程中,假设当前[l,mid]中的剩余元素为[i,j],[mid+1,r]中的剩余元素为[k,l'],其中[mid+1,r]中的前k-1个元素已经入到合并后的数组中,剩下的为[k,l']。
当我们将[l,mid]中的某个元素ai加入合并后的数组时,记下另一个区间中所有大于2ai的元素数量cnt,那么[cnt,mid+1]中的元素均为重要逆序对。
因为[mid+1,r]中的元素已经是有序的,因此在其后续的数中也不可能再有重复的重要逆序对。此时我们移动到下一个[l,mid]中的元素,同样记下另一个区间中所有大于2ai的元素数量cnt。
我们依此类推,最后统计出[l,mid]中的所有元素与[mid+1,r]中的重要逆序对数量之和即为答案。
时间复杂度
排序的时间复杂度是O(nlogn),在合并时统计重要逆序对的数量的时间复杂度是O(n),因此总时间复杂度是O(nlogn)。
C++ 代码
算法2
(线段树) $O(nlogn)$
线段树中每个节点表示[l,r]区间中每个元素的重要逆序对数量。
考虑每个节点如何合并成父节点的值。
假设一个节点表示的区间为[l,r],左右子节点分别表示的区间为[l,mid]和[mid+1,r],则当前节点表示的重要逆序对有三个来源:
子节点中来自[l,mid]的重要逆序对数量。
子节点中来自[mid+1,r]的重要逆序对数量。
跨越[l,mid]和[mid+1,r]的重要逆序对数量。该数量可以通过枚举[l,mid]中的每个元素ai,统计[mid+1,r]中所有大于2ai的元素数量cnt,那么在该区间中对该元素的贡献就是cnt。
为了方便合并,对于每个节点中的信息,我们需要维护三个信息:
划分区间[l,r]。
[l,r]中的元素按照从小到大的顺序排序后得到的数组。
[l,r]中重要逆序对数量。
这里我们仅讨论如何维护第一个和第三个信息,第二个信息可以在插入过程中维护。
由于线段树每个节点表示的区间长度为1,因此我们可以直接用一个整数数组来存储每个节点的信息。对于节点l,其左右子节点分别为2l和2l+1,父节点为l/2。
时间复杂度
每次查询树中的最大值需要O(logn)的时间,共需要查询n次,因此总时间复杂度是O(nlogn)。
C++ 代码
最近,Tom 和 Jerry 在上数据分析课。今天的课程内容是一个人类称之为“逆序对”的东西。 逆序对的定义如下:对于给定的一段正整数序列{a_i},逆序对就是序列中满足 a_i> a_j且 i < j 的有序对。学习了这个概念后,他们决定比赛谁先算出给定的一段正整数序列中逆序对的数目。可怜的 Tom 还在研究如何更快的暴力求解,你能帮 Jerry 想出一个更快的方法吗? 注:序列中可能有重复数字。 输入输出格式 输入: 第一行输入为一个整数 N(1 <= N <= 100,000),表示正整数序列共有 N 个正整数; 第二行输入为由N个正整数构成的序列{a_i}。满足对任意的a_i有1 ≤ a_i ≤ 1,000,000,000。
这道题目可以使用归并排序的思想来求解逆序对的数量。具体来说,在归并排序的过程中,将原序列分成左右两个子序列,分别计算左右子序列内部的逆序对数量,再计算左右两个子序列之间的逆序对数量,最后将左右两个有序子序列合并成一个有序序列。在计算左右子序列内部的逆序对数量时,可以使用分治的思想递归求解。具体实现可以参考下面的 Python 代码:
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, inv_left = merge_sort(arr[:mid])
right, inv_right = merge_sort(arr[mid:])
merged, inv_merge = merge(left, right)
return merged, inv_left + inv_right + inv_merge
def merge(left, right):
i, j = 0, 0
merged = []
inv = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
inv += len(left) - i
merged.extend(left[i:])
merged.extend(right[j:])
return merged, inv
n = int(input())
a = list(map(int, input().split()))
_, ans = merge_sort(a)
print(ans)
```
其中 `merge_sort` 函数用于归并排序,返回排序后的序列以及逆序对数量。`merge` 函数用于合并两个有序的子序列,返回合并后的有序序列以及两个子序列之间的逆序对数量。在合并两个子序列时,如果左子序列的当前元素小于等于右子序列的当前元素,则直接将左子序列的当前元素加入到合并后的序列中;否则,将右子序列的当前元素加入到合并后的序列中,并且右子序列的当前元素和左子序列的剩余元素都构成逆序对,因此需要计算逆序对的数量。最后,将左右两个有序子序列合并成一个有序序列时,还需要将剩余的元素依次加入到合并后的序列中。