hdu 2158 不錯的想法題

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;
}