记录每天看(抄)题解的日常;
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+10; int q1[maxn],q2[maxn],h1=1,h2=1,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=2147483647; int main() { 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); for(int l=1,r=0;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==2147483647) printf("-1"); else printf("%d",ans); return 0; }