萌新求助 用STL的双端队列写 RE一个点

P1440 求m区间内的最小值

违规用户名59285 @ 2019-10-10 23:08:45


#include<cstdio>
#include<queue>
using namespace std;

int n,m;
struct point{
    int v;
    int no;
};

int tag;

point a[2000005];
deque<point> q;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
      {
        scanf("%d",&a[i].v);
        a[i].no=i;
      }
    a[0].no=0;
    a[0].v=0;  

    tag=-1; 
    while(tag<n-1)
      {
        tag++;
          if(q.empty())
            q.push_back(a[tag]);
          else
            {
              while(q.front().no<tag-m+1)
               q.pop_front();         
              if(a[tag].v<=q.front().v)
                {
                    q.clear();
                    q.push_back(a[tag]);
                }
              else if(a[tag].v<=q.back().v)           
                   {
                    while(a[tag].v<=q.back().v)
                     {
                        q.pop_back();
                     }
                    q.push_back(a[tag]); 
                   }
              else q.push_back(a[tag]);         
            }
        if(tag==0) 
          {
            q.pop_front();
            printf("0\n");
          } 
        else 
          printf("%d\n",q.front().v);

      }

  return 0;     
}

那道滑动窗口也是re一个点 不明白呀。。。

by 千反田 @ 2019-10-11 06:37:38

在下面弹出队头/队尾元素的时候前面多加个!q.empty()才能保证队列不为空


by 千反田 @ 2019-10-11 06:37:53

@江沢铭路


by Haishu @ 2019-10-11 08:00:42

ID暴力


by 违规用户名59285 @ 2019-10-11 20:53:16

@风吹花烬 谢谢dalao 的确是这样 之前以为根据这些代码就省得判断是否为空了 看来是while那儿出了问题


|