摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 快排+二分搜尋++++++++++++

題目是找出最長不重複數字!

上同一篇的文章  是不會在UVA通過的

這一篇  終於通過了!!

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int num;
   int L;
}node[1000001]={0};
int compare(const void *ele1, const void *ele2)  
{  
  struct node  *px,*py;  
 
  px=(struct node *)ele1;  
  py=(struct node *)ele2;  
  /* 由小排到大 */   
  if(px->num >= py->num) return 1;  
  else return 0;    
}
int Search(int n,int L)  
{  
 int lower=0, mid, high=L-1;  
 int index=-1;  
    do   /*二分搜尋*/ 
    {  
      mid=(lower+high)/2;  
      if(node[mid].num<n)     lower=mid+1;  
      else if(node[mid].num>n)  high=mid-1;  
      else  index=mid;  
    }  
    while(index==-1&&lower<=high);  
  return index;  
} 
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
int in[1000001];
int check(int NUM,int last,int now,int N)
{
   int find=Search(NUM,N),a,b,MAX=-1;
   for(a=find;a<N;a++)
      if(node[a].num!=NUM) break;
      else
         {
            if(node[a].L>MAX&&node[a].L<now)
               MAX=node[a].L;
         }
   for(a=find-1;a>=0;a--)
      if(node[a].num!=NUM) break;
      else
         {
            if(node[a].L>MAX&&node[a].L<now)
               MAX=node[a].L;
         }
   if(last>MAX)  return last;
   else return MAX;
}
main()
{
  int T;
  scanf("%d",&T);
       while(T--)
          {
            int N,a,b,MAX=1,last=-1;
            scanf("%d",&N);
            for(a=0;a<N;a++)
              {
                in[a]=input();
                node[a].num=in[a];
                node[a].L=a;
              }
            qsort(node,N,sizeof(struct node), compare);
           /* for(a=0;a<N;a++)
                printf("%d %d\n",node[a].num,node[a].L);*/
            for(a=0;a<N;a++)
                {
                  int test=check(in[a],last,a,N);
                /*  printf("%d\n",test);*/
                  if(a-test>MAX) MAX=a-test;
                  last=test;
                }
            printf("%d\n",MAX);
              /* printf("%d %d\n",node[a].num,node[a].L);*/
         }
 return 0;
}