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 |
一个wa的程序,谁帮我看看,思路:每一万一万来处理,保存到h和l,再线性找,sum减去,测试数据过了#include<stdio.h> #include<stdlib.h> void bubble(int *a,int first,int end) { for(int flag=first;flag<end;flag++) for(int i=end;i>flag;i--) if(a[i]<a[i-1]) { int t=a[i]; a[i]=a[i-1]; a[i-1]=t; } } int partition(int *a,int p,int r,int x) { int i,j; for(i=p,j=r;i<j;i++) { if(a[i]>x) { while(i<j&&a[j]>x) j--; if(i!=j) { int t=a[i]; a[i]=a[j]; a[j]=t; j--; } } } return i-1; } int select(int *a,int p,int r,int k) { int i; if(r-p<75) { bubble(a,p,r); return a[p+k-1]; } for(i=0 ; i<(r-p-4)/5 ; i++ ) { int s=p+5*i,t=s+4; bubble(a,s,t); int temp=a[p+i]; a[p+i]=a[s+2]; a[s+2]=temp; } int x=select(a, p , p+(r-p-4)/5 , (r-p+6)/10 ); i=partition(a,p,r,x); int j=i-p+1; if(k<=j) return select(a,p,i,k); else return select(a,i+1,r,k-j); } int main() { int a,b,c,*l,*h,m,i,n; scanf("%d %d %d",&a,&b,&c); while(a!=0) { n=c; int k[10000]; long sum=0; h=new int[500*a];int hl=0; l=new int[500*b];int ll=0; m=0; while(n>=10000) { m++; for(i=0;i<10000;i++) { scanf("%d",&k[i]); sum+=k[i]; } for(i=0;i<a;i++) h[hl++]=select(k,0,9999,10000-i); for(i=0;i<b;i++) l[ll++]=select(k,0,9999,i+1); n-=10000; } for(i=0;i<n;i++) { scanf("%d",&k[i]); sum+=k[i]; } for(i=0;i<a;i++) h[hl++]=select(k,0,n-1,n-i); for(i=0;i<b;i++) l[ll++]=select(k,0,n-1,i+1); for(i=0;i<a;i++) sum-=select(h,0,hl-1,hl-i); for(i=0;i<b;i++) sum-=select(l,0,ll-1,i+1); double ave=sum*1.0/(c-a-b); printf("%.6lf\n",ave); scanf("%d %d %d",&a,&b,&c); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator