Time Limit: 10 second
Memory Limit: 2 MB
问题描述
给定一个序列a1,a2...an。如果存在i小于j 并且ai大于aj,那么我们称之为逆序对,求给定序列中逆序对的数目
Input
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。Output
所有逆序对的总数
Sample Input
4 3 2 3 2
Sample Output
3
【题解】
在进行归并排序的同时求逆序对。
我们在进行归并排序时。
分成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; }