【a703】求逆序对

Time Limit: 10 second

Memory Limit: 2 MB

问题描述

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

Input

第一行为n，表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。

Output

所有逆序对的总数

Sample Input

Sample Output

【题解】

在进行归并排序的同时求逆序对。

我们在进行归并排序时。

分成l..mid和mid+1..r

假设左边循环变量为i，右边的循环变量为j。

则当我们找到一个i和j满足a[i] > a[j]时。

因为左边,右边都是有序的，则a[i+1..mid]都大于a[j]；

而之后我们会吧a[j]加入到temp数组中，此后a[j]不再出现。

则逆序对的数目增加mid-i+1；

然后逆序对数目用数据范围大的类型存储就好了。

【代码】

#include <cstdio>

int n,a[100009],temp[100009];

double tot = 0;

void input_data()

{

	scanf("%d",&n);

	for (int i = 1;i <= n;i++)

		scanf("%d",&a[i]);

}

void mergesort(int l,int r) //对区间[l,r]进行分割

{

	if (l == r) return; //只剩一个元素则认为其是有序的。

	int mid = (l+r)/2; //获取中间的位置

	mergesort(l,mid);mergesort(mid+1,r); //将这个位置的左边和右边进行不断切割。

	int i = l,j = mid+1,k = l;

	while (i <= mid && j <= r) //开始进行二路归并。

		if (a[i] <= a[j]) //比较小的数放到temp数组中去

			temp[k++] = a[i++];

				else //在排序的同时顺便求逆序对

					{

						tot+=mid-i+1;

						temp[k++] = a[j++];

					}

	while (i <= mid)

		temp[k++] = a[i++];

	while (j <= r)  //剩下相同的数字也要放进temp数组

		temp[k++] = a[j++];

	for (int w = l;w<=r;w++) //最后再把temp数组赋值给原数组

		a[w] = temp[w];

}

void output_ans()

{

	printf("%.0lf",tot);

}	

int main()

{

	//freopen("F:\\rush.txt","r",stdin);

	input_data();

	mergesort(1,n);

	output_ans();

	return 0;

}

巴特西

【a703】求逆序对

Input

Output

Sample Input

Sample Output

最新文章

热门文章