【例题4】光荣的梦想1635

Description：Prince对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。
　　一串数列即表示一个世界的状态。
　　平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

Input：第一行为数列中数的个数n,第二行为n <= 10000个数。表示当前数列的状态。

Output：输出一个整数，表示最少需要交换几次能达到平衡状态。

Sample Input

　　4

　　2 1 4 3

Sample Output：2

【分析】

1.原始的解决方案（双重循环）

C:=0;

For i:=1 to n -1 do

       for j:=i+1 to n do if a[i]>a[j] then c:=c+1;

时间复杂度为O(n2)

2.采用二分法求解:

记数列a[st,ed]的逆序对数目为D(st,ed);

    mid=[(st+ed)/2],则有：

    D(st,ed)=D(st,mid)+D(mid+1,ed)+F(st.mid,ed).

其中F(st,mid,ed)表示一个数取自A[st,mid],令一个数取自A[mid+1,ed]的逆序对数目。

若要求计算d值的同时数列A已排序，设I,j指针分别已排序的A[st,med)和A(mid+1,ed)中的一个元素，若满足：

A[mid+1],…A[j-1]均小于A[i],但A[j]>A[i]

则j-mid-1必须计入F，顺序移动I,j指针即可完成合并。

#include<iostream>

using namespace std;

int temp[10001],a[10001],tot=0;

void merge_sort(int left,int right)

{ if(left==right)return;

  int mid=(left+right)/2;

  merge_sort(left,mid);

  merge_sort(mid+1,right);

  int p=left,i=left,j=mid+1;

  while(i<=mid&&j<=right)

{

if(a[i]>a[j]) { tot=tot+mid-i+1;temp[p++]=a[j++]; }

            else temp[p++]=a[i++];

    }

    while(i<=mid)temp[p++]=a[i++];

    while(j<=right)temp[p++]=a[j++];

    for(i=left;i<=right;i++) a[i]=temp[i];

}

int main()

{  int n;

   cin>>n;

   for(int i=1;i<=n;i++) cin>>a[i];

   merge_sort(1,n);

   cout<<tot; 

   return 0;

}