#include <iostream>
using namespace std;

const int MAX = 500001;
long long a[MAX],b[MAX];
long long res;

void merge(int begin,int mid,int end)
{
 int i,j,k = 0;
 for(i = begin,j = mid+1; i <= mid && j <= end; k++){
  if(a[i] <= a[j])
   b[k] = a[i++];
  else {
   b[k] = a[j++];
   res += mid+1-i;
  }
 }
 for(; i <= mid; i++)
  b[k++] = a[i];
 for(; j <= end; j++)
  b[k++] = a[j];
 for(i = 0; i < k; i++)
  a[begin+i] = b[i];
}

void msort(int s, int t)
{
 if(s < t){
  int m = (s+t)>>1;
  msort(s,m);
  msort(m+1,t);
  merge(s,m,t);
 }
}

int main()
{
	int test;
	int i;
	while (scanf("%d",&test) && test)
	{
		res=0;
		for (i=0;i<test;i++)
		{
			scanf("%lld",&a[i]);
		}
		msort(0,test-1);
		printf("%lld\n",res);
	}
}
想不出来个理由？

• Re:megersort居然错？ (925) frkstyc 2006-10-22 21:47:41
  • Re:megersort居然错？ (12) 6233843 2006-10-23 18:10:34
  • cout的，没看出来为和致命，请指教 (0) tdzl2003 2006-10-23 21:55:45
    • rpwt为致命 (0) frkstyc 2006-10-23 21:57:07
      • …… (0) tdzl2003 2006-10-23 21:57:24
      • 幸好我向来cout…… 看过传说中ltc的一次代码，专门写了个函数输出long long (0) tdzl2003 2006-10-23 21:57:49