| ||||||||||
| 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