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,请指点,thx

Posted by project at 2005-04-29 14:28:39 on Problem 2287
#include<stdio.h>    
#define MAX 1001
void Merge(long a[],long p,long q,long r)
{
	long i,j,t;
	long lt[MAX];
	t=p;i=p;j=q+1;
	while(t<=r)
	{
		if(i<=q&&(j>r||a[i]>=a[j]))   
		{
			lt[t]=a[i];
			i++;
		}
		else
		{
			lt[t]=a[j];
			j++;
		}
		t++;
	}
	for(i=p;i<=r;i++)
		a[i]=lt[i];
}

void merge_sort(long a[],long p,long r)  
{
	long q;
	if(p!=r)
	{
		q=(p+r-1)/2;
		merge_sort(a,p,q);
		merge_sort(a,q+1,r);
		Merge(a,p,q,r);
	}
}

int main()
{
	long a[1001],b[1001];long n,i,sum1,sum2,k;
	while(scanf("%d",&n)!=EOF)
	{
		if(!n) break;
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0;i<n;i++)
			scanf("%d",&b[i]);
		merge_sort(a,0,n-1);            //先排序
		merge_sort(b,0,n-1);
		sum1=0;sum2=0;
		k=0;
		for(i=0;i<n;i++)
		{
			while(k<n&&a[i]<=b[k]&&a[i]!=-1&&b[k]!=-1) k++;
			if(k<n&&a[i]>b[k]&&a[i]!=-1&&b[k]!=-1)
			{
				a[i]=-1; b[k]=-1; k++; sum1++;   //把已赢了的标记-1去掉
			}
		}
		k=0;
		for(i=0;i<n;i++)
		{
			while(k<n&&a[i]!=b[k]&&a[i]!=-1&&b[k]!=-1) k++;
			if(k<n&&a[i]==b[k]&&a[i]!=-1&&b[k]!=-1)
                           {
				a[i]=-1; b[k]=-1; k++; sum2++;
			}
		}
		printf("%ld\n",200*(sum1)-200*(n-sum1-sum2));
	}
	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