P2698 [USACO12MAR] Flowerpot S

monotonic queue, https://www.luogu.com.cn/problem/P2698

老板需要你帮忙浇花。给出 $N$ 滴水的坐标， $(x, y)$ 表示水滴最初的坐标。

每滴水均以每秒 $1$ 个单位长度的速度下落。你需要把花盆放在 $x$ 轴上的某个位置，使得花盆接到第 $1$ 滴水与最后 $1$ 滴水之间的时间差至少为 $D$ 。

如果水滴落在 $x$ 轴上的位置与花盆的边沿对齐，也认为被接住。

给出 $N$ 滴水的坐标和时间差 $D$ ，请算出最小的花盆宽度 $W$ 。

输入格式

第一行 $2$ 个整数 $N$ 和 $D$ 。

接下来 $N$ 行，每行 $2$ 个整数，表示水滴的坐标 $(x, y)$ 。

输出格式

一行 $1$ 个整数，表示最小的花盆宽度。如果无法构造出满足题意的花盆，则输出 $- 1$ 。

输入 #1

输出 #1

说明/提示

【样例解释】

有 $4$ 滴水，初始位置分别在 $(6, 3)$ ， $(2, 4)$ ， $(4, 10)$ ， $(12, 15)$ 。水滴至少用 $5$ 秒时间先后落入花盆。花盆的宽度为 $2$ 是必须且足够的，此时把花盆放在 $x = 4 \dots 6$ 的位置，它可以接到水滴 $1$ 和 $3$ ，之间的时间差为 $10 - 3 = 7$ ，满足条件。

【数据范围】

$40 %$ 的数据： $1 \leq N \leq 1000$ ， $1 \leq D \leq 2000$ 。

$100 %$ 的数据： $1 \leq N \leq 10^{5}$ ， $1 \leq D \leq 10^{6}$ ， $0 \leq x, y \leq 10^{6}$ 。

这是一道经典的双指针（滑动窗口）结合单调队列的题目。

题目分析

物理含义：水滴 $(x, y)$ 表示在 $x$ 坐标处，经过 $y$ 秒后水滴会落地。
核心目标：我们要选定一个区间 $[L, R]$ （即花盆的宽度为 $R - L$ ），使得落在这个区间内的水滴中，落地的最晚时间与最早时间之差 $\geq D$ 。
数学转化：在按 $x$ 坐标排序后的水滴序列中，找到一个子序列 $[i, j]$ ，满足 $max (y_{i} \dots y_{j}) - min (y_{i} \dots y_{j}) \geq D$ ，且最小化 $x_{j} - x_{i}$ 。

解题思路

排序：首先将所有水滴按 $x$ 坐标从小到大排序。
双指针：使用左右两个指针 l 和 r 维护一个窗口。
- 右指针 r 不断向右移动，增加窗口内的水滴。
- 当窗口内的 $max (y) - min (y) \geq D$ 时，尝试收缩左指针 l，以减小窗口宽度并更新全局最小值。
单调队列：为了高效地在 $O (1)$ 时间内获取当前窗口内的最大值和最小值，我们维护两个单调队列：
- max_q：单调递减队列，队头存储当前窗口 $y$ 的最大值。
- min_q：单调递增队列，队头存储当前窗口 $y$ 的最小值。
Python 代码实现

python

import sys
from collections import deque

def solve():
    # 使用 fast I/O
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    d = int(input_data[1])
    
    points = []
    idx = 2
    for _ in range(n):
        x = int(input_data[idx])
        y = int(input_data[idx+1])
        points.append((x, y))
        idx += 2
        
    # 按 x 坐标排序
    points.sort()
    
    # 单调队列存储的是 points 的索引
    max_q = deque() # y 值单调递减，队头为最大值
    min_q = deque() # y 值单调递增，队头为最小值
    
    l = 0
    ans = float('inf')
    
    for r in range(n):
        # 维护最大值队列
        while max_q and points[max_q[-1]][1] <= points[r][1]:
            max_q.pop()
        max_q.append(r)
        
        # 维护最小值队列
        while min_q and points[min_q[-1]][1] >= points[r][1]:
            min_q.pop()
        min_q.append(r)
        
        # 当满足条件：最大 y - 最小 y >= d 时
        while l <= r and points[max_q[0]][1] - points[min_q[0]][1] >= d:
            # 更新答案：花盆宽度为当前两个端点的 x 差值
            ans = min(ans, points[r][0] - points[l][0])
            
            # 左指针右移，尝试收缩宽度
            l += 1
            # 移除不在窗口内的索引
            if max_q and max_q[0] < l:
                max_q.popleft()
            if min_q and min_q[0] < l:
                min_q.popleft()
                
    if ans == float('inf'):
        print("-1")
    else:
        print(ans)

if __name__ == "__main__":
    solve()

关键点详解

排序的重要性：排序后，随着 r 的增加，x[r] 是递增的。这使得我们可以利用双指针在 $O (N)$ 的时间内扫描整个数组，而不需要暴力枚举所有区间。
队列维护：
- max_q 队头始终是当前窗口 $[l, r]$ 中 $y$ 最大的那个点的下标。
- min_q 队头始终是当前窗口 $[l, r]$ 中 $y$ 最小的那个点的下标。
时间复杂度：排序耗时 $O (N \log N)$ ，双指针扫描每个元素进出队列各一次，耗时 $O (N)$ 。总复杂度 $O (N \log N)$ ，完全可以满足 $N = 10^{5}$ 的数据范围。
空间复杂度：需要 $O (N)$ 存储点的数据和队列。

样例运行

对于输入：

排序后：(2,4), (4,10), (6,3), (12,15)
当 r=1 (点 (4,10)) 时：max=10, min=4，差值 $6 \geq 5$ 。ans = 4-2 = 2。
当 r=2 (点 (6,3)) 时：窗口内最大 $y = 10$ (来自点 (4,10))，最小 $y = 3$ (来自点 (6,3))，差值 $7 \geq 5$ 。尝试收缩 l，ans = min(2, 6-4) = 2。
最终输出 2。

P2698 [USACO12MAR] Flowerpot S ​

P2698 [USACO12MAR] Flowerpot S