逆序对的数量(题解)

举报
irrational 发表于 2022/01/18 00:27:48 2022/01/18
【摘要】 给定一个长度为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].


  
  1. #include <iostream>
  2. using namespace std;
  3. typedef long long LL;
  4. const int N = 1e5 + 10;
  5. int a[N], tmp[N];
  6. LL merge_sort(int q[], int l, int r)
  7. {
  8. if (l >= r) return 0;
  9. int mid = l + r >> 1;
  10. LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
  11. int k = 0, i = l, j = mid + 1;
  12. while (i <= mid && j <= r)
  13. if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
  14. else
  15. {
  16. res += mid - i + 1;
  17. tmp[k ++ ] = q[j ++ ];
  18. }
  19. while (i <= mid) tmp[k ++ ] = q[i ++ ];
  20. while (j <= r) tmp[k ++ ] = q[j ++ ];
  21. for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
  22. return res;
  23. }
  24. int main()
  25. {
  26. int n;
  27. scanf("%d", &n);
  28. for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
  29. cout << merge_sort(a, 0, n - 1) << endl;
  30. return 0;
  31. }

话不多说,直接上代码,在归并排序中求解逆序对即可。另外呢,最后一个扫尾工作,双指针中的i,j可能有一个已经提前用完了。

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/120593375

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。