博客

题目：

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。

解析：

这道题

只要双重循环就可以解决

但是

因为题目要求

所以

被迫使用更麻烦的方法

这道题

其实就是归并排序

至于为何

就不说了

归并排序

就是将一个数组

不断分割

一直分割到只剩一个为止

一个的话

必定是有序的

再不断

进行合并

就这样不断重复

最终就会合并成一个有序数组

不过我不喜欢

因为这个

太麻烦了

有简单的方法

就一定要用简单的方法

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int a[1000],hb[1000],sum,n;
void gbpx(int l,int r)
{
	int i,j,mid,z;
	mid=(l+r)/2;
	gbpx(l,mid);
	gbpx(mid+1,r);
	i=l;
	j=mid+1;
	z=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			hb[z]=a[i];
			z++;
			i++;
		}
		else
		{
			hb[z]=a[j];
			z++;
			j++;
			sum+=(mid-i);
		}
		while(i<=mid) 	          
        {   
			hb[z]=a[i]; 
			i++; 
			z++; 
		}
        while(j<=r)
        {   
			hb[z]=a[j];  
			j++;  
			z++; 
		}
        for(int d=l;d<=r;d++) a[d]=hb[d];      
	}
}
int main()
{
	freopen("gb.in","r",stdin);
	freopen("gb.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	gbpx(1,n);
	cout<<sum<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

拜拜！！！