逆序对的数量(题解)
【摘要】
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。 逆序对的定义如下:对于数列的第i个和第j个元素,如果满足i<j且a> a,则其为一个逆序对;否则不是。 输入格式 第一行包含整数n,表示数列的长度。 第二行包含n个整数,表示整个数列。 输出格式 输出一个整数,表示逆序对的个数。 数据范围 1n≤100000, 数列...
给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第i个和第j个元素,如果满足i<j且a> a,则其为一个逆序对;否则不是。
输入格式
第一行包含整数n,表示数列的长度。
第二行包含n个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1n≤100000,
数列中的元素的取值范围[1,10^9].
-
#include <iostream>
-
-
using namespace std;
-
-
typedef long long LL;
-
-
const int N = 1e5 + 10;
-
-
int a[N], tmp[N];
-
-
LL merge_sort(int q[], int l, int r)
-
{
-
if (l >= r) return 0;
-
-
int mid = l + r >> 1;
-
-
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
-
-
int k = 0, i = l, j = mid + 1;
-
while (i <= mid && j <= r)
-
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
-
else
-
{
-
res += mid - i + 1;
-
tmp[k ++ ] = q[j ++ ];
-
}
-
while (i <= mid) tmp[k ++ ] = q[i ++ ];
-
while (j <= r) tmp[k ++ ] = q[j ++ ];
-
-
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
-
-
return res;
-
}
-
-
int main()
-
{
-
int n;
-
scanf("%d", &n);
-
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
-
-
cout << merge_sort(a, 0, n - 1) << endl;
-
-
return 0;
-
}
-
话不多说,直接上代码,在归并排序中求解逆序对即可。另外呢,最后一个扫尾工作,双指针中的i,j可能有一个已经提前用完了。
文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/weixin_54227557/article/details/120593375
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)