> #include<stdio.h>
> #include<string.h>
> int a[500005],t[500005];
> __int64 merge_sort(int l,int r,int len)
> {
> 	int i,temp,j;
> 	__int64 ans=0;
> 	if(len==0)
> 		return 0;
> 	temp=(l+r)/2;
> 	ans+=merge_sort(l,temp,temp-l);
> 	ans+=merge_sort(temp+1,r,r-temp-1);
> 	int p=l,q=temp+1;
> 	j=l;
> 	for(i=0;i<=len;i++)
> 	{
> 		if(q>r||(p<=temp&&a[p]<a[q]))
> 			t[j++]=a[p++];
> 		else
> 		{
> 			ans+=temp-p+1;
> 			t[j++]=a[q++];
> 		}
> 	}
> 	for(;l<=r;l++)
> 		a[l]=t[l];
> 	return ans;
> }
> inline void scan(int &n)
> {
> 	char c;
> 	//while(c=getchar(),c<'0'||c>'9');
> 	n=0;
> 	while(c=getchar(),c<='9'&&c>='0')
> 		n=n*10+c-'0';
> }
> int main()
> {
> 	int n,i;
> 	__int64 ans;
> 	while(scanf("%d",&n),n)
> 	{
> 		getchar();
> 		for(i=0;i<n;i++)
> 			scan(a[i]);
> 		ans=merge_sort(0,n-1,n-1);
> 		printf("%I64d\n",ans);
> 	}
> }
用这个程序交是641ms，我改成正常的scanf("%d",&a[i]);就是341ms。

• Re:merge144MS，不幸排在第一 (57) l2ice 2011-08-30 12:35:47