[USACO12MAR]花盆Flowerpot[单调队列+二分]

题目描述

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

img

Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John’s flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.

老板需要你帮忙浇花。给出 $N$ 滴水的坐标,$y$表示水滴的高度,$x$表示它下落到$x$轴的位置。
每滴水以每秒1个单位长度的速度下落。你需要把花盆放在 $x$ 轴上的某个位置,使得从被花盆接着的第1滴水开始,到被花盆接着的最后1滴水结束,之间的时间差至少为$D$。
我们认为,只要水滴落到$x$轴上,与花盆的边沿对齐,就认为被接住。给出N滴水的坐标和$D$的大小,请算出最小的花盆的宽度$W$。

输入输出格式

输入格式:

第一行2个整数 $N$ 和 $D$。
第 $2.. N+1$行每行 2 个整数,表示水滴的坐标$(x,y)$。

输出格式:

仅一行1个整数,表示最小的花盆的宽度。如果无法构造出足够宽的花盆,使得在D单位的时间接住满足要求的水滴,则输出 $-1$。

输入输出样例

输入样例#1:

1
2
3
4
5
4 5
6 3
2 4
4 10
12 15

输出样例#1:

1
2

说明

【样例解释】

有4滴水, (6,3), (2,4), (4,10), (12,15).水滴必须用至少5秒时间落入花盆。花盆的宽度为2是必须且足够的。把花盆放在x=4..6的位置,它可以接到1和3水滴, 之间的时间差为10-3 = 7满足条件。

【数据范围】

40%的数据:$1 ≤ N ≤ 1000$,$1 ≤ D ≤ 2000$;

100%的数据:$1 ≤ N ≤ 100000$,$1 ≤ D ≤ 1000000$,$0≤x,y≤10^6$。

题解

对于每列的水滴,只需要维护最低的高度和最高的高度
对于宽度为 $x$ 的花盆,相当与求 是否存在区间 $i$ - $i+x$ $(1 \le i \le n-x)$ 满足 $D \le max-min $ ($max$为区间中的最大值,$min$为区间中的最小值)
对于这个$x$ 我们可以二分答案,check我们可以用单调队列优化的求区间最值

对于区间最值的维护方法:

1.队首的一定为最优解
2.弹掉队首不符合条件的点
3.队尾弹掉不比当前插入的点更优的点

时间复杂度 $O(n \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){k=k*10+(s^48);s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=1e6+1000;
int n,d,X,Y,l,r,mid,ans;
int Min[maxn],Max[maxn],MMin,MMax,XX;
int q1[maxn],l1,r1,q2[maxn],l2,r2;
bool check(int x)
{
l1=1;r1=0;l2=1;r2=0;
q1[1]=0;q2[1]=0;
memset(q1,0,sizeof(q1));memset(q2,0,sizeof(q2));
for (int i=1;i<=XX;i++)
{
while (l1<=r1&&(i-q1[l1])>x) l1++;
while (l1<=r1&&Min[q1[r1]]>=Min[i]) r1--;
r1++;q1[r1]=i;//求min:Min[q[l1]]

while (l2<=r2&&(i-q2[l2])>x) l2++;
while (l2<=r2&&Max[q2[r2]]<=Max[i]) r2--;
r2++;q2[r2]=i;//求max:Max[q[l2]]

if (i>=x&&Max[q2[l2]]-Min[q1[l1]]>=d)//符合条件
{return true;}
}
return false;
}
int main()
{
n=read();d=read();
memset(Min,0x3f3f3f3f,sizeof(Min));MMin=Min[0];
for (int i=1;i<=n;i++)
{
X=read();Y=read();
qmin(Min[X],Y);qmax(Max[X],Y);//保留最值
qmin(MMin,Y);qmax(MMax,Y);qmax(XX,X);
}
if (MMax-MMin<d) {printf("-1");return 0;}//所有的都取都无法满足条件输出-1
l=0;r=XX;
while (l<r)//二分答案
{
mid=(l+r)>>1;
if (check(mid)) r=mid; else l=mid+1;
}
printf("%d\n",l);
return 0;
}