单调队列

· · 题解

P3088

单调队列

先看板题：P1886

单调队列用队列实现，每次窗口向右滑动时，新进来的元素就入队。

我们手模一下这组数据（以最大值为例）：

5 3
3 5 4 2 1

先将 3 入队：

再将 5 入队。这时因为 5 比 3 大，而且 5 后进来，“退役”得比 3 晚，所以在一切情况下都不比 3 差，3 已经没用了，所以弹出 3 再将 5 入队：

接下来将 4 入队。虽然 4 比 5 小，但是因为后进来，可能在 5“退役”之后能成为最大值，所以入队：

再将 2 入队，同理：

再将 1 入队，注意这时 5 已经“退役”了，所以弹出：

注意到整个过程中最大值都是最左边的值。

本题思路

这道题中并不关心有多少个超过两倍高度的，也不关心超过多少，所以想到维护区域内最高的牛，与这头牛身高的两倍比较。可以用单调队列维护。

但是这只能解决一头牛左边有没有足够高的牛，所以还要从右到左再来一遍。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Cow{
    int x,h;
    bool operator<(Cow a){//为了排序
        return x<a.x;
    }
}cow[50010];
int n,d;
deque<Cow>dq;//单调队列要用双端队列
int pushleft(int x){
    while(!dq.empty()&&dq.back().h<=cow[x].h)//空了就不能再弹了
        dq.pop_back();
    dq.push_back(cow[x]);
    while(!dq.empty()&&dq.front().x+d<cow[x+1].x)//判断是否“退役”，注意刚压入的牛也可能马上“退役”，所以要判空
        dq.pop_front();
    return dq.empty()?0:dq.front().h; //因为上述原因，如果空了返回0，保证不会让牛错误地感到拥挤
}
int pushright(int x){
    while(!dq.empty()&&dq.back().h<=cow[x].h)
        dq.pop_back();
    dq.push_back(cow[x]);
    while(!dq.empty()&&dq.front().x-d>cow[x-1].x)
        dq.pop_front();
    return dq.empty()?0:dq.front().h; 
}
bool crowd[50010];//是否觉得拥挤，true表示宽敞，false表示拥挤
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>d;
    for(int i=1;i<=n;i++)
        cin>>cow[i].x>>cow[i].h;
    sort(cow+1,cow+n+1);
    for(int i=1;i<n;i++)
        if(pushleft(i)<2*cow[i+1].h)
            crowd[i+1]=1;//如果低于2倍身高就不觉得拥挤
    dq.clear();//注意清空
    for(int i=n;i>1;i--)
        if(pushright(i)<2*cow[i-1].h)
            crowd[i-1]=1;
    int ans=0;
    for(int i=2;i<n;i++)//两端的两头牛不可能觉得拥挤
        ans+=int(!crowd[i]);
    cout<<ans<<endl;
    return 0;
}