花盆式样_单调队列

题目链接

Solution

转化一下,就是个单调队列.
可以发现就是一段区间 \([L,R]\) 使得其高度的极差不小于 \(d\) ,同时满足 \(R-L\) 最小.
然后可以考虑二分然后再 \(O(n)\) 判断, 时间复杂度 \(O(nlogn)\) .

Code

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=1000008; ll n,d; ll ans; struct point{ ll x,y; }a[maxn]; bool jud(int len) { int qmax[maxn],qmin[maxn]; int h1,h2,t1,t2; h1=h2=1,t1=t2=0; qmax[0]=qmin[0]=0; for(int i=1;i<=n;++i) { while(h1<=t1 && a[i].y>a[qmax[t1]].y)--t1; qmax[++t1]=i; while(h2<=t2 && a[i].y< a[qmin[t2]].y)--t2; qmin[++t2]=i; while(h1<=t1 && a[i].x-a[qmax[h1]].x>len)++h1; while(h2<=t2 && a[i].x-a[qmin[h2]].x>len)++h2; if(a[qmax[h1]].y-a[qmin[h2]].y>=d) return 1; } return 0; } bool cmp(point s,point t) {return s.x<t.x;} int main() { scanf("%lld%lld",&n,&d); for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); int l=1,r=maxn; while(l<=r) { int mid=(l+r)>>1; if(jud(mid)){ans=mid;r=mid-1;} else l=mid+1; } if(ans) printf("%lld\n",ans); else puts("-1\n"); return 0; }