xtu oj 1167 逆序数（大数据）
回顾
Dedicated to you.
突然发现 markdown 语法输入 <3 会出现爱心 ❤️
之前说现实中给朋友讲一下这题，不知道是啥原因，她不方便听还是不愿意听，总之就是没讲。所以我把这题写一篇笔记，因为笔者写这题的时候真的算是非常的激动了，前置知识点是归并排序，刚好我复习了好几遍归并排序，看到这题的时候，算是刷算法题的时候能得到的为数不多的正反馈了。
另外因为笔者用的主题是黑色的背景，所以加粗不会正常显示，所以直接这样子标记了hhh
题目描述
给你一个序列x1,x2...,xn,如果数对<xi,xj>，其中i<j,而xi>xj我们称之为逆序数对。一个序列的逆序数对的数目，称为这个房列的逆序数。比如说序列312,逆序数对为 <3,1>和<3,2>，所以这个序列的逆序数为2。现在给你一个数字序列，请求其逆序数。
输入
每个样例为两行，第一行为一个整数n(n<10,000)，表示序列中数字的个数，如果n为0，则表示输入结束，不需要处理。 第二行是n个整数xi，0≤xi≤100,000。输入数据保证序列中没有相同整数。
输出
每行输出一个整数，表示其序列数。
样例输入
3
312
4
1234
0
样例输出
2
0
思路
- 归并排序的意思就是，把排好序的两段归并到一块，从而使得整个序列都是有序的。这个题要求的是逆序对的数目，把数据范围扩大了一些，假设我们暴力去枚举的话，就会超出时间限制。
- 代码里面的
merge表示的就是归并排序的意思。我们是在归并排序的过程中，顺便把逆序对的数目求出来了。 q数组存的是，我们输入的序列，或者理解为需要被排序的一串数字。tmp数组是临时数组，充当中间人的作用，意思就是把q数组里面的两段先临时存到tmp数组里面，完了之后再把tmp数组里面的元素放回q数组，实现归并排序。- 归并排序需要先递归，递归到能够直接排好序，然后再归并，不断归并到最后合成一段。
- 逆序对这里相较于归并排序多了一步，就是，我们假设两段排好序的数组，这里的排好序指的是从小到大排好序。一段是从，
[l,mid],一段是从[mid+1,r]，我们把左边一段叫做PQ，右边一段叫做HH，我们比较PQ和HH里面的元素，把小的元素存到临时数组里面，假设PQ里面的元素小，这属于正常情况，不用管，假设HH里面的元素小，这就出现逆序对了,mid-i+1这么多个元素都在j指向的这个元素左边且比q[j]大，均满足逆序对的定义，所以答案加上mid-i+1 - 后面就是，一段更新完了之后，把另一段全部存到临时数组里面，再把临时数组里面的元素存回原来的数组即可
- 时间复杂度是
O(n*logn)
c 语言代码
#include<stdio.h>
#define N 100010
int q[N],tmp[N];
#define LL long long
LL merge(int l,int r){
if(l>=r){
return 0;
}
int mid=(l+r)/2;
LL res=merge(l,mid)+merge(mid+1,r);
int i=l,j=mid+1;
int k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j]){
tmp[k++]=q[i++];
}else{
tmp[k++]=q[j++];
res=res+(mid-i+1);
}
}
while(i<=mid){
tmp[k++]=q[i++];
}
while(j<=r){
tmp[k++]=q[j++];
res=res+(mid-i+1);
}
for(i=l,j=0;i<=r;i++,j++){
q[i]=tmp[j];
}
return res;
}
int main(){
int n;
while(scanf("%d",&n)){
if(n==0){
break;
}
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
printf("%lld\n",merge(0,n-1));
}
return 0;
}
原文地址：https://blog.csdn.net/L3102250566/article/details/142760064
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！