题目描述
农夫约翰一直难以让他种植的植物茁壮成长,他需要你来给植物适当的浇水。
给定二维平面中 N 个雨滴的位置,其中 y 表示雨滴的垂直高度,x 表示其在一维数轴上的位置。
每个雨滴以每秒 1 个单位长度的速率向下(朝 x 轴)下落。
你需要将宽度为 W 的农夫约翰的花盆沿 x 轴放置在某处,以便第一个雨滴击中花盆与最后一个雨滴击中花盆之间的时间差至少为 D(使得花盆中的花获得充足的水)。
一滴水落在花盆的边缘就等于击中了花盆。
给定 D 的值和 N 个雨滴的位置,请计算 W 的最小可能值。
样例输入
4 5
6 3
2 4
4 10
12 15
样例输出
2
样例解释
将宽度为 2 的花盆放置在 x=4..6 处,可以接到雨滴 1 和 3,两雨滴接到的时间差为 10−3=7。
算法
(单调队列 + 二分) $O(nlogn)$
问题1: 如果我们已经知道了W,那么怎么求时间差是否大于等于D?
显然,我们只需判断每个长为W的区间,最早落下的和最晚落下的水滴的时间差是否大于等于D即可。
也就只需要知道最小的 y 与最大的 y 即可(典型的滑动窗口问题)?
将水滴按照x从小到大排序,水滴序列便满足单调队列的性质1:序列为顺序
于是问题就成了:给定一个序列(y值),区间长度为W,求每个区间的最大值和最小值。
分别用维护最大值的单调递减队列和维护最小值的单调递增队列即可。
问题2: W怎么知道?
二分!
令l=0,因为这题宽度为实际宽度 - 1,例如样例中的4 — 6实际宽度为3,输出却是2,而对于3 — 3这样实际宽度为1的,应输出0,故 l 从0开始
r = 最大的 x,如果连W=最大的x时都无法满足题意时,l便会等于r,即l=最大的x,这样我们只需在二分完后判断l是否等于最大的x,就可以知道有无答案了。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
PII a[N];
int maxq[N], minq[N];
bool check(int n, int d, int w) {
int maxfront = 0, maxrear = -1, minfront = 0, minrear = -1;
for (int i = 0; i < n; ++i) {
if (maxfront <= maxrear && a[i].first - a[maxq[maxfront]].first > w) maxfront ++;
while (maxfront <= maxrear && a[maxq[maxrear]].second <= a[i].second) maxrear --;
maxq[ ++maxrear ] = i;
if (minfront <= minrear && a[i].first - a[minq[minfront]].first > w) minfront ++;
while (minfront <= minrear && a[minq[minrear]].second >= a[i].second) minrear --;
minq[ ++minrear ] = i;
if(a[maxq[maxfront]].second - a[minq[minfront]].second >= d) return true;
}
return false;
}
int main() {
int n, d, w;
scanf("%d%d", &n, &d);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i].first, &a[i].second);
sort(a, a + n);
int l = 0, r = a[n-1].first;
while( l < r) {
int mid = (l + r) >> 1;
if(check(n, d, mid)) r = mid;
else l = mid + 1;
}
if(l == a[n - 1].first) printf("-1");
else printf("%d", l);
return 0;
}