https://www.luogu.org/problemnew/show/P2698#sub
老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。
每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。
我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。
单调队列好题，参考洛谷题解。
emm……显然是单调队列，把x排个序，维护y的单调增，然后正反扫一遍，当y差值>=d更新答案并且弹出对首，当y不满足单调是弹出对尾。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
inline int read(){
int X=0,w=0;char ch=0;
while(ch<'0'||ch>'9'){w|=ch=='-';ch=getchar();}
while(ch>='0'&&ch<='9')X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
struct node{
int x,y;
}a[N],q[N];
bool cmp(node a,node b){
return a.x<b.x;
}
int main(){
int n=read(),d=read();
for(int i=1;i<=n;i++){
a[i].x=read(),a[i].y=read();
}
sort(a+1,a+n+1,cmp);
int l=0,r=0,ans=1e9;
for(int i=1;i<=n;i++){
while(l<r&&q[r-1].y>a[i].y)r--;
q[r++]=a[i];
while(l<r&&q[r-1].y-q[l].y>=d){
ans=min(ans,q[r-1].x-q[l].x);
l++;
}
}
for(int i=n;i>=1;i--){
while(l<r&&q[r-1].y>a[i].y)r--;
q[r++]=a[i];
while(l<r&&q[r-1].y-q[l].y>=d){
ans=min(ans,q[l].x-q[r-1].x);
l++;
}
}
if(ans==1e9)puts("-1");
else printf("%d\n",ans);
return 0;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++