刷题记录:NC24325[USACO 2012 Mar S]Flowerpot

传送门:牛客

题目描述:

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

首先这道题就是计算一个满足水滴的纵坐标的最大值和最小值之差大于等于D的区间的最小长度

这道题有大概两种解法:

首先是我们应该能想到的二分算法

因为我们发现显然我们的可行性是关于我们的宽度W是具有单调性的(显然盆子的宽度越大我们的水滴的覆盖宽度就越大,那么显然的,我们能满足时间差为D的概率就越大),这样我们就证明了我们二分的正确性,接下来就是我们二分的check部分了,其实呢,当我们确定了我的水盆的长度之后,这道题就变成了滑动窗口,可以说我们的check函数和解决这道题并没有什么两样

主要思路:

对于我们的每一个二分出来的mid,我们都可以先固定我们的左端点L,并且移动我们的右端点,每次移动一个右端点,都判断当前的点和左指针的点的距离差是不是小于我们的mid,假设不小于,我们就应该左移我们的左指针,并且当我们移动的时候我们都维护两个单调队列(一个用来维护最大值,一个用来维护区间内的最小值),每次右移一位都判断最大值和最小值
是否满足我们的D即可,一旦满足就直接return true即可

具体的代码(二分):

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,d;
struct Node{
	int x,y;
}node[maxn];
bool cmp(Node a,Node b) {
	return a.x<b.x;
}
deque<Node>q1;
deque<Node>q2;
int check(int mid) {
	while(q1.size()) q1.pop_back();
	while(q2.size()) q2.pop_back();
	int ans=inf;int l=1;
	for(int i=1;i<=n;i++) {
		while(node[i].x-node[l].x>mid) l++;
		while(!q1.empty()&&q1.front().x<node[l].x) {
			q1.pop_front();
		}
		while(!q2.empty()&&q2.front().x<node[l].x) {
			q2.pop_front();
		}
		while(!q1.empty()&&node[i].y>=q1.back().y) {
			q1.pop_back();
		}
		q1.push_back(node[i]);
		while(!q2.empty()&&node[i].y<=q2.back().y) {
			q2.pop_back();
		}
		q2.push_back(node[i]);
		if(q1.front().y-q2.front().y>=d) return true;
	}
	return false;
}
int main() {
	n=read();d=read();
	for(int i=1;i<=n;i++) {
		node[i].x=read();node[i].y=read();
	}
	sort(node+1,node+n+1,cmp);
	int l=0,r=node[n].x-node[1].x;
	int ans=inf;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) {
			ans=min(ans,mid);
			r=mid-1;
		}else {
			l=mid+1;
		}
	}
	if(ans==inf) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}

### 接下来是比较难想的直接使用单调队列的解法(可能有人也能直接想到吧,反正我当时只能想到二分解法)

主要思路:

1. 我们主要是固定我们的区间的左端点(我们记作L),然后不断的移动我们的右端点(我们记作R),知道[L,R]区间内的数字的最大值和最小值之差满足我们的条件,注意此时我们的存储方式将是准备两个队列,一个用来记录最大值队列(即不上升队列),一个用来记录最小值队列(即不下降队列),为什么要记录下来我们的最大值和最小值呢,因为一旦我们的这个区间满足了我们的条件.显然我们的右端点就没必要继续移动了,因为不论右端点右边的数字是什么,只会不断的增加我们的W值而已,此时我们应该做的是将我们的左端点不断右移,直到区间内的一个最大值或者最小值移除我们的区间,此时当我们的区间内的最大值/最小值移除之后,显然我们需要接班的一个最大值/最小值来顶替移除的,那么此时我们的队列就有用处了,因为我们是储存小于右端点位置的单调队列,所以此时我们直接踢掉队列中最开始的那个即可,然后继续判断我们的两个单调队列的队首是不是满足我们的条件,如果不满足则移动右端点
2. 然后反复的重复移动判断操作,直至我们的左端点到达最后

接下来是代码部分(直接单调队列做法):

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,d;
struct Node{
	int x,y;
}node[maxn];
deque<Node>q1;//记录最大值
deque<Node>q2;//记录最小值
bool cmp(Node a,Node b) {
	return a.x<b.x;
}
int main() {
	n=read();d=read();
	int ans=inf;
	for(int i=1;i<=n;i++) {
		node[i].x=read();node[i].y=read();
	}
	sort(node+1,node+n+1,cmp);
	int r=1;int flag;
	for(int l=1;l<=n;l++) {
		while(!q1.empty()&&q1.front().x<node[l].x) {
			q1.pop_front();
		}
		while(!q2.empty()&&q2.front().x<node[l].x) {
			q2.pop_front();
		}
		if(q1.front().y-q2.front().y>=d){
			flag=1;
		}else {
			flag=0;
		}
		while(!flag&&r<n) {
			r++;
			while(!q1.empty()&&q1.back().y<node[r].y) {
				q1.pop_back();
			}
			q1.push_back(node[r]);
			while(!q2.empty()&&q2.back().y>node[r].y) {
				q2.pop_back();
			}
			q2.push_back(node[r]);
			if(q1.front().y-q2.front().y>=d){
				flag=1;
			}
		}
		if(flag) ans=min(ans,node[r].x-node[l].x);
	}
	if(ans==inf) cout<<"-1"<<endl;
	else cout<<ans<<endl;
	return 0;
}