思路:
求x的一个区间,使区间中的松果的最大y坐标和最小y坐标的差至少为D。若有多个区间,则取最小的那个。
即使用单调队列不断维护最大值和最小值。
首先L固定不动,R不断右移:
即若函数f(R)=max[L,R]-min[L,R] >=D,则此区间满足要求。
之后L往右移一位,R不断右移,找下一个满足条件的区间。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, d, ans = 0x3f3f3f3f;
struct pos
{
int x, y;
bool operator<(const pos &a) const
{
return x < a.x;
}
} p[N];
deque<int> maxn, minn;//存储最大值和最小值的索引
int main()
{
cin >> n >> d;
for (int i = 1; i <= n; i++)
{
cin >> p[i].x >> p[i].y;
}
sort(p + 1, p + n + 1);
int l = 1; // 左端点从1开始
for (int i = 1; i <= n; i++)
{
// 确保maxn队列中的y坐标是递增的
while (!maxn.empty() && p[i].y > p[maxn.back()].y)
maxn.pop_back();
maxn.push_back(i);
// 确保minn队列中的y坐标是递减的
while (!minn.empty() && p[i].y < p[minn.back()].y)
minn.pop_back();
minn.push_back(i);
//如果满足条件,就更新答案
while (l < i && p[maxn.front()].y - p[minn.front()].y >= d)
{
ans = min(ans, p[i].x - p[l].x);
l++;
while (!maxn.empty() && maxn.front() < l)
maxn.pop_front();
while (!minn.empty() && minn.front() < l)
minn.pop_front();
}
}
if (ans == 0x3f3f3f3f)
cout << -1 << endl;
else
cout << ans << endl;
return 0;
}