POJ 2823Sliding Window单调队列解题报告

利用单调队列的出队入队，维护区间的最值，保证队列单调递增或单调递减，要维护单调递增队列，当一个数字插入的时候，从队尾往前找到第一个比它小的值把后面的值都删掉，然后把这个值放在找到的位置的后面，单调递减队列也是类似的情况，因为是单调序列，查找过程可以用二分查找。

View Code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #define N 1000005
  5 using namespace std;
  6 int val[N],Min[N],Max[N];
  7 int id[N];
  8 int dmin(int f,int r,int d)
  9 {
 10     int mid;
 11     while(f<=r)
 12     {
 13         mid=(f+r)>>1;
 14         if(Min[mid]==d)
 15         return mid;
 16         if(Min[mid]>d)
 17         r=mid-1;
 18         else
 19         f=mid+1;
 20     }
 21     return f;
 22 }
 23 int dmax(int f,int r,int d)
 24 {
 25     int mid;
 26     while(f<=r)
 27     {
 28         mid=(f+r)>>1;
 29         if(Max[mid]==d)
 30         return mid;
 31         if(Max[mid]<d)
 32         r=mid-1;
 33         else
 34         f=mid+1;
 35     }
 36     return f;
 37 }
 38 int main()
 39 {
 40     int f1,f2,r1,r2,n,k,i,j;
 41     scanf("%d%d",&n,&k);
 42     for(i=1;i<=n;i++)
 43     scanf("%d",&val[i]);
 44     if(k==1)//本以为加上能快一些，没想到还不如不加
 45     {
 46         for(i=1;i<=n;i++)
 47         {
 48             if(i!=1)
 49             printf(" ");
 50             printf("%d",val[i]);
 51         }
 52         printf("\n");
 53         for(i=1;i<=n;i++)
 54         {
 55             if(i!=1)
 56             printf(" ");
 57             printf("%d",val[i]);
 58         }
 59         printf("\n");
 60         return 0;
 61     }
 62     f1=r1=1;
 63     Min[1]=val[1];
 64     id[1]=1;
 65     for(i=2;i<=k;i++)
 66     {
 67         r1=dmin(f1,r1,val[i]);
 68         //printf("%d\n",Min[1]);
 69         Min[r1]=val[i];
 70         id[r1]=i;
 71     }
 72     printf("%d",Min[1]);
 73     for(i=k+1;i<=n;i++)
 74     {
 75         r1=dmin(f1,r1,val[i]);
 76         Min[r1]=val[i];
 77         id[r1]=i;
 78         while(i-id[f1]>=k)
 79         f1++;
 80         printf(" %d",Min[f1]);
 81     }
 82     printf("\n");
 83     f2=r2=1;
 84     Max[1]=val[1];
 85     id[1]=1;
 86     for(i=2;i<=k;i++)
 87     {
 88         r2=dmax(f2,r2,val[i]);
 89         Max[r2]=val[i];
 90         id[r2]=i;
 91     }
 92     printf("%d",Max[1]);
 93     for(i=k+1;i<=n;i++)
 94     {
 95         r2=dmax(f2,r2,val[i]);
 96         Max[r2]=val[i];
 97         id[r2]=i;
 98         while(i-id[f2]>=k)
 99         f2++;
100         printf(" %d",Max[f2]);
101     }
102     printf("\n");
103     return 0;
104 }