Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:为什么归并的非递归写法就会超时 而递归就可以过?????我晕 TLE几个小时了In Reply To:为什么归并的非递归写法就会超时 而递归就可以过?????我晕 TLE几个小时了 Posted by:x666633 at 2009-05-20 15:08:25 #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; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator