洛谷 2698 Flowerpot

发表于 | 分类于 ， | 评论数：

摘要

给出一些二维点，求 $x$ 长最短的区间，满足该区间内点 $y$ 坐标极差 $\ge D$

不太一样的滑动窗口题目。

[USACO 2012 MAR SILVER] Flowerpot

题面

题解

滑动窗口 双指针

窗口保持极差 $\ge D$ ，需要支持出队、入队、求极差

用两个单调队列维护最大最小值。

（这种单调性相反的队列中的元素是不交的（除队尾），不清楚这个性质有什么用处）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

//https://www.luogu.com.cn/problem/P2698
//2021 10 20 AliCCC

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF=1034567890;
const int MAXN=100111;

int N, D;
struct Pos{
	int x, y;
} P[MAXN];

bool cmpx(const Pos &A, const Pos &B){
	return A.x<B.x;
}

int Mx[MAXN], Mxh, Mxt;
int Mn[MAXN], Mnh, Mnt;

int main(){
	
	
	scanf("%d%d", &N, &D);
	
	for(int i=1;i<=N;++i){
		scanf("%d%d", &P[i].x, &P[i].y);
	}
	
	sort(P+1, P+N+1, cmpx);
	
	int Ans=INF;
    //int Ans=N+1;
	
	for(int i=1, j=1;i<=N;++i){
		while(j<=N && P[Mx[Mxh]].y-P[Mn[Mnh]].y<D){
			while(Mxh<Mxt && P[Mx[Mxt-1]].y<=P[j].y)	--Mxt;
			Mx[Mxt++]=j;
			while(Mnh<Mnt && P[Mn[Mnt-1]].y>=P[j].y)	--Mnt;
			Mn[Mnt++]=j;
			++j;
		}
		if(P[Mx[Mxh]].y-P[Mn[Mnh]].y>=D)	Ans=min(Ans, abs(P[j-1].x-P[i].x));	//Ans=min(Ans, j-i);
		if(Mx[Mxh]==i)	++Mxh;
		if(Mn[Mnh]==i)	++Mnh;
	}
	
	printf("%d\n", (Ans>=INF)?-1:Ans);
	
	return 0;
}