题目链接

题面

题意

找到最长的一个区间，使得这个区间内的最大值减最小值在\([m,k]\)中。

思路

我们用两个单调队列分别维护最大值和最小值，我们记作\(q1\)和\(q2\)。

如果\(q1\)的底部的值与\(q2\)的底部的值大于\(k\)，则将\(q1,q2\)底部中下标最小的\(pop\)掉，并记录下来，记作\(tmp\)，如果\(q1,q2\)底部的值大于等于\(m\)则更新答案\(ans = max(ans,i-tmp)\)。

代码实现如下

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long LL;typedef pair
                   
                     pLL;typedef pair
                    
                      pLi;typedef pair
                     
                       pil;;typedef pair
                      
                        pii;typedef unsigned long long uLL;#define lson rt<<1#define rson rt<<1|1#define lowbit(x) x&(-x)#define name2str(name) (#name)#define bug printf("*********\n")#define debug(x) cout<<#x"=["<
                       
                        <<"]" <

q1, q2;int main() {#ifndef ONLINE_JUDGE FIN;#endif // ONLINE_JUDGE while(~scanf("%d%d%d", &n, &m, &k)) { int ans = 0; while(!q1.empty()) q1.pop_back(); while(!q2.empty()) q2.pop_back(); int tmp = 0; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); while(!q1.empty() && a[i] > a[q1.front()]) q1.pop_front(); q1.push_front(i); while(!q2.empty() && a[i] < a[q2.front()]) q2.pop_front(); q2.push_front(i); while(!q1.empty() && ! q2.empty() && a[q1.back()] - a[q2.back()] > k) { if(q1.back() > q2.back()) tmp = q2.back(), q2.pop_back(); else tmp = q1.back(), q1.pop_back(); } if(!q1.empty() && !q2.empty() && a[q1.back()] - a[q2.back()] >= m) { ans = max(ans, i - tmp); } } printf("%d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/Dillonh/p/11172583.html

你可能感兴趣的文章