hdu 2158 不错的想法题

思路 ：

两个变量i j 对每一个i满足查找的都用j来维护 是的这个区间的长度是对i的最小满足要求的区间 这样就不用跑O^n的时间复杂度了

#include
  
   
#include
   
     #include
     
     using namespace std
     ; int num
     [100010
     ],mark
     [100010
     ]; int main() { int n
     ,m
     ,Q
     ,i
     ,j
     ; while(~scanf
     ("%d%d"
     ,&n
     ,&m
     )) { if(n
     ==0
     &&m
     ==0
     ) break; for(i
     =1
     ;i
     <=n
     ;i
     ++) scanf
     ("%d"
     ,&num
     [i
     ]); while(m
     --) { scanf
     ("%d"
     ,&Q
     ); memset
     (mark
     ,0
     ,sizeof(mark
     )); int a
     ; int cont
     =0
     ; for(i
     =1
     ;i
     <=Q
     ;i
     ++) { scanf
     ("%d"
     ,&a
     ); if(mark
     [a
     ]==0
     ) cont
     ++; mark
     [a
     ]=1
     ; } int leap
     [100010
     ]; memset
     (leap
     ,0
     ,sizeof(leap
     )); int Min
     ; int flash
     =0
     ; for(i
     =1
     ;;i
     ++) { if(mark
     [num
     [i
     ]]==0
     ) continue; for(j
     =i
     ;j
     <=n
     ;j
     ++) { if(mark
     [num
     [j
     ]]) { if(leap
     [num
     [j
     ]]==0
     ) flash
     ++; leap
     [num
     [j
     ]]++; } if(flash
     ==cont
     ) break; } break; } Min
     =j
     -i
     +1
     ; leap
     [num
     [i
     ]]--; if(leap
     [num
     [i
     ]]==0
     ) flash
     --; for(i
     ++;i
     <=n
     ;i
     ++) { if(!mark
     [num
     [i
     ]]) continue; if(flash
     ==cont
     ) { if(j
     -i
     +1
     <Min
     ) Min
     =j
     -i
     +1
     ; leap
     [num
     [i
     ]]--; if(leap
     [num
     [i
     ]]==0
     ) flash
     --; continue; } for(j
     ++;j
     <=n
     ;j
     ++) { if(!mark
     [num
     [j
     ]]) continue; if(leap
     [num
     [j
     ]]==0
     ) flash
     ++; leap
     [num
     [j
     ]]++; if(flash
     ==cont
     ) break; } if(flash
     ==cont
     &&j
     -i
     +1
     <Min
     ) Min
     =j
     -i
     +1
     ; leap
     [num
     [i
     ]]--; if(leap
     [num
     [i
     ]]==0
     ) flash
     --; } printf
     ("%d\n"
     ,Min
     ); } } return 0
     ; }