单调队列

 

by  

 

是比较裸的单调队列

   就拔高了一个层次（多了一维）

有一个a*b的整数组成的矩阵

现请你从中找出一个n*n的正方形区域

使得该区域所有数中的最大值和最小值的差最小

 

只写MAX了，MIN一个道理，懒 不写了

先横着跑单调队列

　　维护许多长度为 n 的 横着的MAX

　　存在数组 map1[][] 中

再对数组 map1[][] 竖着跑单调队列

　　就维护了 许多 n*n 的 矩阵的MAX

MIN同理

在竖着跑单调队列时

顺便MAX 与 MIN 作差

更新答案即可

 

代码

 

一个小地方debug了好久

代码上还有 

学 mzx dalao  “ 二分出错位置  输出中间答案 ” 的 “ 蛛丝马迹 ”

 

1 #include
     
        2 using namespace std;  3 #define A 1005  4 #define N 105  5 int an=1000000001,h2,t2,h1,t1,a,b,n;  6 int pos1[A],pos2[A],que1[A],que2[A];  7 int mip1[A][A],map1[A][A];  8 int mip2[A][A],map2[A][A];  9 int read(){  //  读入优化  10     int ans=0; 11     char ch=getchar(); 12     for(;!isdigit(ch);ch=getchar()); 13     for(;isdigit(ch);ch=getchar()) 14         ans=ans*10+ch-'0'; 15     return ans; 16 } 17 int main(){ 18     a=read(),b=read(),n=read(); 19     for(int k,i=1;i<=a;i++){ 20         h1=h2=1; 21         t1=t2=0; 22         for(int j=1;j<=b;j++){ 23             k=read(); 24              25             for(;t1>=h1&&k>=que1[t1];t1--); 26             que1[++t1]=k; 27             pos1[t1]=j; 28              29             for(;t2>=h2&&k<=que2[t2];t2--); 30             que2[++t2]=k; 31             pos2[t2]=j; 32              33             if(j>=n){ 34                 map1[i][j]=que1[h1]; 35                 mip1[i][j]=que2[h2]; 36                 if(pos1[h1]==j-n+1)h1++; 37                 if(pos2[h2]==j-n+1)h2++; 38             } 39         } 40     } 41     /*cout<
      
       =h1&&k1>=que1[t1];t1--); 62             que1[++t1]=k1; 63             pos1[t1]=j; 64              65             for(;t2>=h2&&k2<=que2[t2];t2--); 66             que2[++t2]=k2; 67             pos2[t2]=j; 68              69              70             if(j>=n){ 71               //map2[j][i]=que1[h1]; 72               //mip2[j][i]=que2[h2]; 73               an=min(an,que1[h1]-que2[h2]); 74               if(pos1[h1]==j-n+1)h1++; 75               if(pos2[h2]==j-n+1)h2++; 76             } 77         } 78     } 79      80     /*for(int i=1;i<=a;i++){ 81       for(int j=1;j<=b;j++) 82         cout<
       
        <<" "; 83       cout<