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

用qsort为什么WA?

Posted by sunflowwer at 2006-08-17 20:02:44 on Problem 1828
#include <stdio.h>
#include <stdlib.h>

struct monkey{
      __int64 a;
	  __int64 b;
	  __int64 c;
}sort[500000];
int cmp1(const void *a,const void *b)
{
      struct monkey *c=(monkey *)a;
	  struct monkey *d=(monkey *)b;
	  if (c->a==d->a)
	  {
         if (c->b>d->b) return 1;
         if (c->b<d->b) return -1;
         return 0;
	  }
      if (c->a>d->a) return 1;
      if (c->a<d->a) return -1;
      return 0; 
}
int cmp2(const void *a,const void *b)
{
      struct monkey *c=(monkey *)a;
	  struct monkey *d=(monkey *)b;
	  if (c->b==d->b)
	  {
         if (c->a>d->a) return 1;
         if (c->a<d->a) return -1;
         return 0;
	  }
      if (c->b>d->b) return 1;
      if (c->b<d->b) return -1;
      return 0; 
}
int main()
{
      int n;
	  int i;
	  int count;
	  while(1)
	  {
	       scanf("%d",&n);
		   if(!n)
			   break;
		   for(i=0;i<n;i++)
			   scanf("%I64d%I64d",&sort[i].a,&sort[i].b);
		   for(i=0;i<n;i++)
			   sort[i].c=0;
		   qsort(sort,n,sizeof(sort[0]),cmp1);
/*		   printf("\n");
           for(i=0;i<n;i++)
			   printf("%I64d %I64d\n",sort[i].a,sort[i].b);
		   printf("\n"); */
		   for(i=0;i<n-1;i++)
			   if(sort[i+1].a>=sort[i].a && sort[i+1].b>=sort[i].b){
			        sort[i].c=1;
					if(sort[i+1].a==sort[i].a && sort[i+1].b==sort[i].b)
						sort[i+1].c=1;
			   }
		   qsort(sort,n,sizeof(sort[0]),cmp2);
/*		   printf("\n");
           for(i=0;i<n;i++)
			   printf("%I64d %I64d\n",sort[i].a,sort[i].b);
		   printf("\n");   */
		   for(i=0;i<n-1;i++)
			   if(sort[i+1].a>=sort[i].a && sort[i+1].b>=sort[i].b){
			        sort[i].c=1;
					if(sort[i+1].a==sort[i].a && sort[i+1].b==sort[i].b)
						sort[i+1].c=1;
			   }
		   for(count=0,i=0;i<n;i++)
			   if(sort[i].c==0)
				   ++count;
		   printf("%d\n",count);
	  }
	  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