#include<stdio.h>
struct node 
{
	long int array[500001];
};
long int n,ans;
void change(struct node a,struct node b,long int front,long int end,long int kaishi)
{
	long int i=front,k=front,j=end+1,p,q;
	if(a.array[end]<a.array[end+1])
	{
		for(;i<=kaishi;i++)
			b.array[i]=a.array[i];
	    return ;
	}
	if(a.array[front]>a.array[kaishi])
	{
		for(;j<=kaishi;j++)
		{
			b.array[k]=a.array[j];
			k++;
		}
	    for(;i<=end;i++)
		{
			b.array[k]=a.array[i];
			k++;
		}
	   ans=ans+(kaishi-end)*(kaishi-end);
	   return ;
	}
	while(i<=end&&j<=kaishi)
	{
		if(a.array[i]<=a.array[j])
		{
			b.array[k]=a.array[i];
			i++;
			k++;
		}
		if(a.array[j]<=a.array[i])
		{
			b.array[k]=a.array[j];
			k++;
			j++;
			ans=ans+end-i+1;
		}
	   if(a.array[i]>a.array[kaishi])
	   {
           p=j;q=i;	
		   for(;j<=kaishi;j++)
		   {
			   b.array[k]=a.array[j];
			   k++;
		   }
		   for(;i<=end;i++)
		   {
			   b.array[k]=a.array[i];
			   k++;
		   }
		   ans=ans+(kaishi-p+1)*(end-q+1);
		   return ;
	   }
	}
	while(i<=end)
	{
		b.array[k]=a.array[i];
		i++;
		k++;
	}
	while(j<=kaishi)
	{
		b.array[k]=a.array[j];
		k++;
		j++;
	}
}
void twos(struct node a,struct node b,long int len)
{
	long int p=1,i;
	while(p+2*len-1<=n)
	{
		change(a,b,p,p+len-1,p+2*len-1);
		p+=2*len;
	}
	if(p+len-1<n)change(a,b,p,p+len-1,n);
	else
	{
		for(i=p;i<=n;i++)b.array[i]=a.array[i];
	}
}
void init()
{
	struct node a,b;
	long int i,j,len,help=0;
	n=0;
	scanf("%ld",&n);
	while(n!=0)
	{
		if(n%2==0)help=n/2;
		else help=n/2+1;
		for(i=1;i<=n;i++)
			scanf("%ld",&a.array[i]);
		len=1;
		ans=0;
		while(len<n)
		{
			twos(a,b,len);
			if(len>=help)break;
			len*=2;
			twos(b,a,len);
			if(len>=help)break;
			len*=2;
		}
		printf("%ld\n",ans);
		scanf("%ld",&n);
	}
}
int main()
{
	init();
	return 0;
}

• Re:为什么归并的非递归写法就会超时 而递归就可以过？？？？？我晕 TLE几个小时了 (13) dsq90 2009-09-06 11:02:24