HDU 3410 && POJ 3776 Passing the Message 单调队列 - c++编程基础

题意：

给定n长的数组（下标从1-n）（n个人的身高，身高各不相同

问：对于第i个人，他能看到的左边最矮的人下标。（如果这个最矮的人被挡住了，则这个值为0）

还有右边最高的人下标，同理若被挡住了则这个值为0

输出n行，每个人左右2边的下标。

单调队列，对于 front - rear 的队列（注意出队都是在rear，入队也是在rear）

当加入元素x，若这队列是单调递增的，显然q.front() <= x , 反之若>x ，则把队首元素弹掉，这样就能保持单调性。

若弹掉了队首元素，在此题中就相当于最矮的人被挡住了，因为{q.end() < q.front() }> x。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         using namespace std; #define N 50010 int l[N], r[N]; int a[N],n; int L,R; int q[N*2]; int pos[N]; void init(){ L=1;R=0; } void work1(){ init(); for(int i = 1; i <= n; i++){ bool fa = false; while(L<=R && q[R]
         
          mp; int Stack[N]; int main(){ int i,j ,u, v, T, Cas = 1; scanf("%d",&T); while(T--){ mp.clear(); scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); work1(); work2(); printf("Case %d:\n",Cas++); for(int i = 1;i <=n; i++)printf("%d %d\n",l[i],r[i]); } return 0; }