Source Code

Problem: 1089  User: yzhw 
Memory: 2752K  Time: 344MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
# include <stdlib.h>
typedef struct pair_def
{
   int f;
   int l;
}pair;
struct atom
{
   pair ele;
   struct atom *next;
};
int cmp(const void *pos1,const void *pos2)
{
    pair *a=(pair *)pos1,*b=(pair *)pos2;
    if(a->f!=b->f) return a->f-b->f;
    else return a->l-b->l;
}
pair data[50001];
int main()
{
    int num;
    struct atom *head;
    scanf("%d",&num);
    int i;
    for(i=1;i<=num;i++)
    {
      int t1,t2;
      scanf("%d %d",&t1,&t2);
      data[i].f=t1<t2?t1:t2;
      data[i].l=t1>t2?t1:t2;
    }
    qsort(data+1,num,sizeof(struct pair_def),cmp);
    head=(struct atom*)malloc(sizeof(struct atom));
    head->ele=data[1];
    struct atom *p=head,*q;
    for(i=2;i<=num;i++)
    {
      p->next=(struct atom*)malloc(sizeof(struct atom));
      p=p->next;
      p->ele=data[i];
    }
    p->next=NULL;
    p=head;
    q=head->next;
    while(q!=NULL)
    {
     if(q->ele.f<=p->ele.l&&q->ele.l>=p->ele.l)
     {
      p->ele.l=q->ele.l;
      p->next=q->next;
      free(q);
      q=p->next;
     }
     else if(q->ele.f<=p->ele.l&&q->ele.l<p->ele.l)
     {
          p->next=q->next;
          free(q);
          q=p->next;
     }
     else 
     {
          p=p->next;
          q=q->next;
     }
    }
    for(p=head;p!=NULL;p=p->next)
    {
     printf("%d %d\n",p->ele.f,p->ele.l);
    }

    return 0;
}

• malloc和free费了不少时间。。 (22) damacheng009 2010-07-20 18:34:12