HDU 2158 模拟题 - c++编程基础

题目：

给定一个序列，有N个整数，数值范围为[0,N)。
有M个询问，每次询问给定Q个整数，可能出现重复值。
要求找出一个最短区间，该区间要包含这Q个整数数值。

题解：

先便利一个整体的 L 和 R，然后枚举L，同时维护R，使得区间满足题目要求，更新最小区间，直道不满足要求为止。

代码：

#include
  
   
#include
   
     #define N 100005 
    int a
    [N
    ], find
    [N
    ], mark
    [N
    ]; int l
    , r
    , n
    , m
    , count
    , num
    ; void Find
    () { int kk
     = 0
    ; for(int i
     = 1
    ; i
     <= n
    ; i
    ++) { if(mark
    [a
    [i
    ]]) { if(!find
    [a
    [i
    ]]) kk
     ++; find
    [a
    [i
    ]] ++; if(kk
     == num
    ) { r
     = i
    ; break ; } } } } void slove
    () { for(int i
     = 1
    ; i
     <= n
    ; i
    ++) { if(mark
    [a
    [i
    ]]) { if(!(--find
    [a
    [i
    ]])) { int flag
     = 0
    ; for(int j
     = r
    +1
    ; j
     <= n
    ; j
    ++) { if(mark
    [a
    [j
    ]]) { find
    [a
    [j
    ]] ++; if(a
    [j
    ] == a
    [i
    ]) { flag
     = 1
    ; r
     = j
    ; break; } } } if(!flag
    ) break; } } if(count
     > r
     - i
    ) count
     = r
     - i
    ; } } int main() { int q
    , p
    ; while(scanf
    ("%d %d"
    , &n
    , &m
    )!=EOF
    ) { if( n
     == 0
     && m
     == 0
     ) break; for(int i
     = 1
    ; i
     <= n
    ; i
    ++) { scanf
    ("%d"
    , &a
    [i
    ]); } while(m
     --) { memset
    (mark
    ,0
    ,sizeof(mark
    )); memset
    (find
    ,0
    ,sizeof(find
    )); scanf
    ("%d"
    , &q
    ); num
     = 0
    ; while(q
    --) { scanf
    ("%d"
    , &p
    ); if(!mark
    [p
    ]) num
     ++; mark
    [p
    ] = 1
    ; } l
     = 1
    , count
     = n
    ; Find
    (); count
     = r
     - l
     + 1
    ; slove
    (); printf
    ("%d\n"
    , count
    ); } } }