题解 P3088 【[USACO13NOV]挤奶牛Crowded Cows】

jzqjzq · 2017-04-14 08:21:33 · 题解

楼下STL的nlogn做法也很巧妙啊

这里说一下O(n)的单调队列做法

首先每个元素肯定要按照位置排序，然后依次进队，判断如果队尾的数大小小于要进队的数，那就把队尾弹出，直到队尾的数大于等于要进队的数

这是为了维护单调性

然后再判断如果队头的数位置的差值大于d，出队，直到差值小于d，此时队头的数为单调队列内的合法最大值

因此只要将要进队的数与目前的队头元素比较即可

这样维护了前面的，后面的反一下就好了

时间复杂度：因为每个元素最多进队出队一次，所以是O(n)的

#include<bits/stdc++.h>
using namespace std;
struct ppap{
    int x,y;
}a[100001];
ppap qq[100001];
bool q[100001],h[100001];
inline bool cmp(ppap a,ppap b){return a.x<b.x;}
int main()
{
    int n,d;scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&qq[r].y<a[i].y)r--;
        qq[++r]=a[i];
        while(l<=r&&qq[l].x<a[i].x-d)l++;
        if(qq[l].y>=a[i].y*2)q[i]=1;
    }
    memset(qq,0,sizeof qq);l=1;r=0;
    for(int i=n;i;i--){
        while(l<=r&&qq[r].y<a[i].y)r--;
        qq[++r]=a[i];
        while(l<=r&&qq[l].x>a[i].x+d)l++;
        if(qq[l].y>=a[i].y*2)h[i]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(q[i]&&h[i])ans++;
    printf("%d",ans);
    return 0;
}