洛谷1908 逆序对

本题地址： http://www.luogu.org/problem/show?pid=1908

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入输出格式

输入格式：

第一行，一个数n，表示序列中有n个数。第二行n个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

输入输出样例

输入样例#1：

6 5 4 2 6 3 1

输出样例#1：

11

说明

对于50%的数据，n≤2500对于100%的数据，n≤40000。

题解

排序+分治

此问题可以用归并排序的特性来解决。

归并排序中元素的位置是稳定的，并且每两个子序列也是有序的，当左边的子序列中的元素大于右边的子序列的元素时，左边子序列中该元素后面的所有元素都要大于右边的那个元素，也就是有这么多的逆序对。

因此我们在归并排序的后面加一句话就可以完成（******见代码）。

下面附上代码。

代码

var        i,n,t:longint;        a:array[0..100000] of longint;           h:array[0..100000] of longint;      procedure merge(l,r:longint);      var i,mid,left,right:longint;      begin         if l>=r then exit;         mid:=(l+r)>>1;         merge(l,mid); merge(mid+1,r);   //二分左区间 二分右区间       left:=l; right:=mid+1;         for i:=l to r do begin             if (left<=mid)and((a[left]<=a[right])or(right>r)) then begin                 h[i]:=a[left];                 left:=left+1;             end             else begin                 h[i]:=a[right];                 right:=right+1;                 t:=t+(mid-left+1);  //******加上这句话，统计逆序对数       end;         end;  //区间归并       for i:=l to r do a[i]:=h[i];      end;      begin        readln(n);        for i:=1 to n do read(a[i]);        merge(1,n);        writeln(t);  //此时a数组也是有序的    end. 

（本文系笔者原创，未经允许不得转载）

转载于:https://www.cnblogs.com/yzm10/p/4751997.html