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

一个wa的程序,谁帮我看看,思路:每一万一万来处理,保存到h和l,再线性找,sum减去,测试数据过了

Posted by dawei007 at 2009-05-12 11:46:46 on Problem 2833
#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:
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