Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:merge144MS,不幸排在第一

Posted by dahai1990 at 2011-07-05 18:46:23 on Problem 2299
In Reply To:merge144MS,不幸排在第一 Posted by:qq2985759 at 2011-03-17 20:06:01
> #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。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator