lyzqs的博客 - two-pointer
type: channel
link: https://nakuru.cn/tag/two-pointer/
items: [USACO12MAR]花盆Flowerpot

[USACO12MAR]花盆Flowerpot
type: item
date: 2018-12-18T09:31:00+00:00
description: 一道有思维难度的题看题解看了好久才看懂的2333怎么说呢，首先对于一个指针l，设最小满足条件的r为f[l]易证得f[i]单调不减然后就可以用两个指针扫了l走的时候，r也一直走然后需要维护l，r之间y的最大值最小值这个用单调队列维护然后就可以做完这题了单调队列的题，思维难度都不小23333还是有必要多写点这种题提高思维qwq#include <bits/stdc++.h> #define il inline #define Max 1000005 #define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++) using namespace std; char In[Max],*tt=In,*ss=In; il int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int n,d,ans=0x3f3f3f3f,q1[Max],q2[Max],h1=1,t1,h2=1,t2; struct node { int x,y; }e[Max]; il bool cmp(node a,node b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } int main() { n=read(),d=read(); for(int i=1;i<=n;i++) { e[i].x=read(),e[i].y=read(); } int r=0; sort(e+1,e+1+n,cmp); for(int l=1;l<=n;l++) { while(h1<=t1&&q1[h1]<l) h1++; while(h2<=t2&&q2[h2]<l) h2++; while(e[q1[h1]].y-e[q2[h2]].y<d&&r<n) { ++r; while(e[q1[t1]].y<e[r].y&&h1<=t1) t1--; while(e[q2[t2]].y>e[r].y&&h2<=t2) t2--; q1[++t1]=r;q2[++t2]=r; } if(e[q1[h1]].y-e[q2[h2]].y>=d) ans=min(ans,e[r].x-e[l].x); } if(ans>1000000000) puts("-1"); else cout<<ans<<endl; }