自动搬运

查看原文

来自洛谷，原作者为

	llzzxx712 屑大三

搬运于2025-08-24 21:40:34，当前版本为作者最后更新于2020-07-24 18:33:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2698

前言：本题赞最高的那篇题解已经写得很清楚了，但本蒟蒻还是花了不少时间去理解，我决定把一些可能造成障碍的地方再解释一下

题意简述

• 给出一条线段上的 n 个点，每个点有一个权值 $y_i$ ,你要找出一段区间，使区间中的 $y_{max}-y_{min}$ 大于 d 。
• 输出这个区间的长度

题目分析

首先看到这道题（和这道题的标签）就发现直接求解长度非常麻烦，可以二分区间长度再去判断。

但是再一想，就会发现所在的区间端点一定在水滴上。

为什么呢？ 因为我们的花盆是要碰到水滴才可以计算答案，在水滴外面的部分就浪费了，所以区间端点一定在水滴上。

那么原问题就转化为了：给出一段数 ($y$) ，选出最短的一段，使其中的 最大值-最小值 大于 d 。

那么怎么求这一段呢？一个暴力的解法是枚举左右端点。复杂度 $O(n^2)$ ，T飞~。 另一种方法是用单调队列，这里和滑动窗口稍微有些不同。滑动窗口的区间长度是固定的，要就内部的最大（小）值；这里给出区间内部的条件，求长度。

我们可以采用一个“拉窗口”的方法，最开始左端点和右端点都在最左边。

【】

我们可以把

1. 这个右端点不断往右拉，直到满足条件

【…………】

2. 记录一下答案，然后把左端点往右拉一下

…【…………】

3. 重复一二步骤，直到右端点到达右边界

因为左右端点都只是从左边移到右边，所以复杂度是 $O(n)$ 的。

代码思路

这里我们不关注具体的 x 值而去记录点的编号，因为区间端点一定在水滴上。排序后编号小的 x 一定小，只在记录答案的时候通过编号查询具体 x 值。

我们用两个优先队列，一个存区间最大值，一个存区间最小值。

最外层循环拉左端点（因为要里面右端点移完再动左端点）

每次先用两个while循环更新队首,直到队首不在左端点左边（因为移动了左端点有一个点的值就不能用了）

然后第二层循环移动右端点，直到达到右边界或满足条件（最大值-最小值 > d）。

里面再用两个循环类似滑动窗口更新最大值队列和最小值队列（只要队中还有元素且新加入的元素比队尾大（维护最大值时为小）那么就队尾出队，不需要管队首出队（这是更新左端点做的事情））。

第二层循环结束后，如果满足条件就更新 $ans$ 。（$ans$要初始化成一个很大的值）。

一切结束后如果 $ans$ 还是初始值，就输出 “-1”，否则输出 $ans$ 。

易错点

1. 两个队首都要像滑动窗口那样设置为 1 。（表明队列中有元素）
2. 要用结构体存输入（因为要按 x 排序）
3. $ans$要初始化成一个很大的值
4. 判断是否有解
5. 更新队首要让队首不在左端点左边（用 < 而不是 <=）。

详细注释代码

#include<bits/stdc++.h>
using namespace std;
void read(int &x){//快读 
	int f=1;x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
#define N 100010
int n,d,ans;
struct node{
	int x,y;
}a[N];
bool cmp(node aa,node bb){
	return aa.x<bb.x;
}
int p1[N],p2[N];//我写单调队列一般用 q[] 存具体值，用 p[]存位置 
int head1,head2,tail1,tail2;//队列 1存最大值，队列 2存最小值 
int main(){
	read(n),read(d);//如题所示 
	for(int i=1;i<=n;i++){
		read(a[i].x),read(a[i].y);//结构体，因为要排序 
	}
	sort(a+1,a+1+n,cmp);//排序 
	ans=0x3f3f3f3f;
	head1=head2=1;
	for(int le=0,r=0;le<=n;le++){//最外层循环拉左端点 
		while(head1<=tail1&&p1[head1]<le) head1++;//如果队首比左端点小，那么右移
		while(head2<=tail2&&p2[head2]<le) head2++;//因为排序过了，编号小x一定小 
		while(a[p1[head1]].y-a[p2[head2]].y< d && r<n){
			r++;
			while(head1<=tail1&&a[p1[tail1]].y<a[r].y) tail1--;
			p1[++tail1]=r;
			while(head2<=tail2&&a[p2[tail2]].y>a[r].y) tail2--;
			p2[++tail2]=r;//更新两个单调队列 
		}
		if(r!=n) ans=min(ans,a[r].x-a[le].x);//满足条件 
	} 
	if(ans>=0x3f3f3f3f){//判无解 
		printf("-1");return 0;
	}
	else{
		printf("%d",ans);
	}
}

蒟蒻写题解不易，若对你有帮助，点个赞呗