SGU 180 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=180

180. Inversions

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<= i < j <= N and A[i]>A[j].

Input

The first line of the input contains the number N. The second line contains N numbers A1...AN.

Output

Write amount of such pairs.

Sample Input

5
2 3 1 5 4

Sample Output

3

这个应该是非常经典的经典题,用归并排序求逆序数。

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
算法描述
归并操作的工作原理如下:

  1. 申请空间,归并排序需要一个辅助数组,大小和要排序的数组相同。
  2. 若选取的范围内的元素个数大于等于2,则进行分治。
  3. 设定两个指针,最初位置分别为两个已经排序序列的起始位置。
  4. 比较两个指针所指向的元素,选择相对小的元素放入到辅助数组,并移动指针到下一位置。
  5. 重复步骤4直到某一指针达到序列尾。
  6. 将另一序列剩下的所有元素直接复制到辅助数组中。
  7. 将辅助数组中的元素复制到原数组。

codo 1

#include<stdio.h>
int D[65540],tmp[65540];
long long cnt;
 
void merge(int left,int mid,int right)
{
  int i,j,k;
  i=left;j=mid+1;k=i;
  while(i<=mid&&j<=right)
    {
      if(D[i]<=D[j])
	tmp[k++]=D[i++];
      else
	{
	  tmp[k++]=D[j++];
	  cnt+=mid-i+1;
	}
    }
  while(i<=mid) tmp[k++]=D[i++];
  while(j<=right) tmp[k++]=D[j++];
  for(i=left;i<=right;i++)
    D[i]=tmp[i];
}
 
void mergeSort(int left,int right)
{
  if(left<right)
    {
      int mid=(left+right)/2;
      mergeSort(left,mid);
      mergeSort(mid+1,right);
      merge(left,mid,right);
    }
}
 
int main()
{
  int i,j,k,n;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",D+i);
  cnt=0;
  mergeSort(0,n-1);
  printf("%I64dn",cnt);
  return 0;
}

codo 2

//根据《算法导论》中的伪码所写
#include<stdio.h>
#include<limits.h>
 
long long cnt;
 
void merge(int *D,int left,int mid,int right)
{
  int i,j,k,L[mid-left+2],R[right-mid+1];
 
  for(i=left,j=0;i<=mid;++i)
    L[j++]=D[i];
  L[j]=INT_MAX;
 
  for(i=mid+1,j=0;i<=right;++i)
    R[j++]=D[i];
  R[j]=INT_MAX;
 
  mid-=left;
  for(i=0,j=0,k=left;k<=right;++k)
    {
      if(L[i]<=R[j]) D[k]=L[i++];
      else
	{
	  D[k]=R[j];
	  cnt+=mid-i+1;
	  ++j;
	}
    }
}
 
void mergeSort(int *D,int left,int right)
{
  if(left<right)
    {
      int mid=(left+right)/2;
      mergeSort(D,left,mid);
      mergeSort(D,mid+1,right);
      merge(D,left,mid,right);
    }
}
 
int main()
{
  int i,j,k,n,D[65540];
  scanf("%d",&n);
  for(i=0;i<n;++i)
    scanf("%d",D+i);
  cnt=0;
  mergeSort(D,0,n-1);
  printf("%I64dn",cnt);
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>