首页 算法

单调队列是一种特殊维护的队列。一般地，当一新值准备入队时，须先从后向前，将对后来答案没有了影响的点弹出，再从前向后，将所有超出了统计范围的点弹出。对于大多数问题，求解过程中会锁定很多答案区间，在线求最值。

# P3088 拥挤的奶牛

# 题面

有 NN 头奶牛沿着一维的栅栏吃草，第 ii 头奶牛在目标点 xix_i，它的身高是 hih_i 。当一头奶牛左边 DD 距离内而且右边 DD 距离内有身高至少是它的两倍的奶牛，它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

# 解

当一奶牛将要入队时：

  • 从后往前，将身高小于该奶牛的弹出（ --tail ），因为将要进队的奶牛更加靠后，影响范围一定更大，对答案的贡献也一定更大。
  • 从前往后，将与该奶牛距离已超过 DD 的奶牛弹出（ ++head ）
  • 将该奶牛入队。
  • 与队头奶牛比较身高，若符合则打上标记，若左右两次统计均符合，则计入答案。

每次统计的是该奶牛左侧的合法性，从后到前再做一遍就可以了。

按照以上规则就可以统计答案了。显然该队列一定为单调递降队列。

# 代码

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 55000;
struct node {
    int x, h;
} a[N];
int n, d, queue[N];
bool l[N], r[N];
bool cmp(node a, node b) {
    return a.x < b.x;
}
int main() {
    
    freopen("p3088.in", "r", stdin);
    
    scanf("%d%d", &n, &d);
    for(int i=1; i<=n; ++i) 
        scanf("%d%d", &a[i].x, &a[i].h);
    
    sort(a+1, a+n+1, cmp);
    
    int head = 0, tail = 1;
    queue[head] = 1;
    
    for(int i=2; i<=n; ++i) {
        while(head < tail and a[queue[tail-1]].h <= a[i].h) --tail;
        queue[tail++] = i;
        while(head < tail and a[i].x - a[queue[head]].x > d) ++head;
        
        if(a[queue[head]].h >= (a[i].h << 1)) l[i] = true;
    }
    
    head = 0, tail = 1;
    queue[head] = n;
    
    for(int i=n-1; i>=1; --i) {
        while(head < tail and a[queue[tail-1]].h <= a[i].h) --tail;
        queue[tail++] = i;
        while(head < tail and a[queue[head]].x - a[i].x > d) ++head;
        
        if(a[queue[head]].h >= (a[i].h << 1)) r[i] = true;
    }
    
    int ans = 0;
    for(int i=1; i<=n; ++i) 
        if(l[i] and r[i]) ++ans;
        
    printf("%d\n", ans);
    
    return 0;
}
# P3522 Temperature
# 题面
有 nn 个段，第 ii 个为 [li,ri][l_i, r_i]，现要在几个连续的段中，每段中各取一个值，构成一序列，要求该序列不能下降，求序列的最大长度。
# 解
以段的左端点维护单调序列。
当一新段将要入队时：
  • 从后向前，将所有左点比新段的左点小的段弹出。
  • 从前向后，将所有右点比新段的左点小的段弹出。
  • 统计答案：用当前位置减去队头的上一段的位置
    • ∵\because 队头的上一段已被弹出
    • ∴\therefore 从队头的上一段的下一段起（可能已被弹出）至当前位置均属于合法序列
# 代码
#include <stdio.h>
const int N = 1100000;
int max(int a, int b) { return a > b ? a : b; }
int n, l[N], r[N], queue[N], ans = -1;
int main() {
    
    freopen("p3522.in", "r", stdin);
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%d%d", l+i, r+i);
    
    int head = 0, tail = 1;
    queue[head] = 0;
    
    for(int i=1; i<=n; ++i) {
        
        while(head < tail and l[i] >= l[queue[tail-1]]) --tail;
        queue[tail++] = i;
        
        while(head < tail and l[queue[head]] > r[i]) ++head;
        
        ans = max(ans, i - queue[head-1]);
        
    }
    
    printf("%d\n", ans);
    
    return 0;
}
 
 更新于