首页 > 代码库 > HDU 2158 模拟题

HDU 2158 模拟题

2024-08-05 23:42:04   219人阅读

题目：

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

题解：

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

代码：

#include<stdio.h>
#include<string.h>
#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);
      }
    }
        
}

HDU 2158 模拟题


联系
我们