题目描述
题意大白话就是,给定一些点的横坐标和纵坐标,随着时间的改变,每滴雨的横坐标是不变的,但是纵坐标是一直变小的,然后让你去求这个一个花盆的宽度,使得这个花盆的宽度尽可能的小,但是要满足接到的雨滴的最大纵坐标减去最小纵坐标的差值大于等于D
样例
输入
4 5
6 3
2 4
4 10
12 15
输出
2
算法1
看到各位都是用双指针+单调队列去写的,我用stl+双指针来写
(双指针+stl) $O(nlogn)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll x,y;
}s[200005];
set<ll> res;
set<ll,greater<ll>> re;//这个是改变他的排序顺序,按照降序排序
map<ll,ll> vis;
ll n,m;
bool cmp(node x1,node x2)
{
return x1.x<x2.x;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i].x>>s[i].y;
}
sort(s+1,s+1+n,cmp);//先把雨滴按照横坐标小的进行排序
ll l=1,r=1;
ll ans=0x3f3f3f3f3f3f3f3f;
while(l<=r&&r<=n)
{
vis[s[r].y]++;//vis用来记录每个雨滴的纵坐标在目前的双指针区间范围内有多少
res.insert(s[r].y);//这个是存储升序的雨滴纵坐标序列
re.insert(s[r].y);//这个是存储降序的雨滴纵坐标序列
while(*re.begin()-*res.begin()>=m)//如果说目前的双指针区间范围内的最高雨滴减去最低雨滴的大小是大于等于m的,那么说明合法,我们将l往右移
{
ans=min(ans,s[r].x-s[l].x);//记录答案
vis[s[l].y]--;//l往右移,所以当前l位置的雨滴纵坐标要少一个
if(vis[s[l].y]==0)//如果说少了l这一个该纵坐标数值为0了,那么说明这个区间内没有s[l].y这个值了,那么就在res和re中删去
{
res.erase(s[l].y);//注意,set函数的erase和insert都是log的时间复杂度,所以不必担心
re.erase(s[l].y);
}
l++;
}
r++;
}
if(ans==0x3f3f3f3f3f3f3f3f)
{
cout<<-1<<'\n';
}
else
{
cout<<ans<<'\n';
}
return 0;
}