洛谷3258:[USACO2012 MAR]Flowerpot 花盆——题解

时间:2022-09-11 21:08:32

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/+

+++++++++++++++++++++++++++++++++++++++++++