P2698 [USACO12MAR]花盆Flowerpot—

记录每天看（抄）题解的日常；

https://www.luogu.org/problem/P2698

我们可以把坐标按照x递增的顺序排个序，这样我们就只剩下纵坐标了；

如果横坐标（l，r）区间，纵坐标的最大值减去最小值大于d,那么就可以更新答案；

看出随着l的增长，r一定是递增的；

可以证明不存在（l2,r2）,l2>l1且r2<r，（maxy-miny）>d，且能对答案造成影响；

因为如果有这种存在，那么r2应该是l第一个匹配的对象，是更优的答案；

这就涉及到滑动窗口方法了；

用q1[]记录纵坐标最大值的位置，q2[]记录纵坐标最小值的位置；

范围是l到r；

更新队列区间范围：

while(h1<=t1&&q1[h1]<l) h1++;
while(h2<=t2&&q2[h2]<l) h2++;

更新r,最大值，最小值；

    while(a[q1[h1]].y-a[q2[h2]].y<d&&r<n)

        {

            ++r;

            while(a[q1[t1]].y<a[r].y&&h1<=t1) t1--;

            q1[++t1]=r;

            while(a[q2[t2]].y>a[r].y&&h2<=t2) t2--;

            q2[++t2]=r;

        }

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e6+;

int q1[maxn],q2[maxn],h1=,h2=,t1,t2;

int n,d;

struct node

{

    int x,y;

}a[maxn];

bool cmp(node qw,node we)

{

    return qw.x<we.x;

}

int ans=;

int main()

{

    scanf("%d%d",&n,&d);

    for(int i=;i<=n;i++)

    {

        scanf("%d%d",&a[i].x,&a[i].y);

    }

    sort(a+,a+n+,cmp);

    for(int l=,r=;l<=n;l++)

    {

        while(h1<=t1&&q1[h1]<l) h1++;

        while(h2<=t2&&q2[h2]<l) h2++;

        while(a[q1[h1]].y-a[q2[h2]].y<d&&r<n)

        {

            ++r;

            while(a[q1[t1]].y<a[r].y&&h1<=t1) t1--;

            q1[++t1]=r;

            while(a[q2[t2]].y>a[r].y&&h2<=t2) t2--;

            q2[++t2]=r;

        }

        if(a[q1[h1]].y-a[q2[h2]].y>=d) ans=min(ans,a[r].x-a[l].x);

    }

    if(ans==) printf("-1");

    else printf("%d",ans);

    return ;

}

巴特西

P2698 [USACO12MAR]花盆Flowerpot——单调队列

最新文章

热门文章