洛谷p1908 逆序对
时间: 2024-01-14 20:17:59 浏览: 37
洛谷p1908 逆序对,根据引用和引用的定义,逆序对是指在给定的正整数序列中,存在一对元素满足ai>aj且i<j的有序对。要计算洛谷p1908中的逆序对数目,可以采用归并排序的方法。首先,将序列分为两个部分,分别计算每个部分的逆序对数目,然后再计算两个部分之间的逆序对数目。具体步骤如下:
1. 将序列平均分为两个部分,递归地计算每个部分的逆序对数目。
2. 合并两个有序的部分,同时计算两个部分之间的逆序对数目。
3. 返回每个部分的逆序对数目之和。
计算逆序对数目的关键在于合并两个有序的部分时的比较操作。在比较过程中,如果发现左边部分的元素大于右边部分的元素,则可以得到一个逆序对,并将逆序对数目加上右边部分中剩余的元素个数。
相关问题
p1750 求逆序对
求逆序对是一个经典的问题,可以使用归并排序的思想来解决。具体来说,对于一个数组 $a$,我们可以将其分为左右两个子数组 $a_1$ 和 $a_2$,然后分别递归地求解 $a_1$ 和 $a_2$ 的逆序对个数,最后再计算 $a_1$ 和 $a_2$ 之间的逆序对个数,并将 $a_1$ 和 $a_2$ 合并成一个有序的数组。
下面是一个基于归并排序的求逆序对的示例代码:
```python
def merge_sort(a):
if len(a) <= 1:
return a, 0
mid = len(a) // 2
left, cnt1 = merge_sort(a[:mid])
right, cnt2 = merge_sort(a[mid:])
merged, cnt3 = merge(left, right)
return merged, cnt1 + cnt2 + cnt3
def merge(left, right):
i, j = 0, 0
merged = []
cnt = 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
cnt += len(left) - i
merged += left[i:]
merged += right[j:]
return merged, cnt
```
其中,`merge_sort` 函数用于对数组进行归并排序,并返回排序后的数组和逆序对个数。`merge` 函数用于合并两个有序的数组,并计算它们之间的逆序对个数。
使用示例:
```python
a = [3, 1, 4, 2, 5]
cnt = merge_sort(a)[1]
print(cnt) # 输出 4
```
上述代码的时间复杂度为 $O(n\log n)$,其中 $n$ 是数组的长度。
P1750 求逆序对
逆序对可以使用归并排序来解决。在归并排序中,我们将数组分成两个部分,然后递归地对它们进行排序,最后将它们合并在一起。在合并两个已排序的子数组时,我们可以计算逆序对的数量。具体地,我们用两个指针 $i$ 和 $j$ 分别指向两个子数组的开头,比较它们指向的元素的大小,如果 $a[i] \leq a[j]$,则已经不存在逆序对,直接将 $a[i]$ 加入合并后的数组中,并将 $i$ 指针向后移动一位;否则,将 $a[j]$ 加入合并后的数组中,并将 $j$ 指针向后移动一位,此时 $a[i+1..mid]$ 与 $a[j]$ 都是逆序对。
下面给出具体的代码实现:
```cpp
const int N = 1e5 + 5;
int a[N], b[N], tmp[N]; // b 为辅助数组
long long merge(int l, int mid, int r) {
int i = l, j = mid + 1, k = l;
long long cnt = 0;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
cnt += mid - i + 1; // 统计逆序对数量
}
}
while (i <= mid) b[k++] = a[i++];
while (j <= r) b[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = b[i];
return cnt;
}
long long merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = (l + r) >> 1;
long long cnt = merge_sort(l, mid) + merge_sort(mid + 1, r) + merge(l, mid, r);
return cnt;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
printf("%lld\n", merge_sort(1, n));
return 0;
}
```
时间复杂度为 $O(n\log n)$。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)