题解 | #浇狡猾花#

题目链接

题目描述

有 $n$ 滴水，第 $i$ 滴水的初始坐标为 $(x_i, y_i)$ 。所有水滴均以每秒 $1$ 个单位长度的速度垂直下落。

你需要将一个花盆放置在 $x$ 轴上，使得花盆接到的第一滴水与最后一滴水之间的时间差至少为 $d$ 。水滴下落到 $x$ 轴的时刻即为其初始的 $y_i$ 坐标值。

求满足条件的最小花盆宽度。如果不存在任何方式可以满足时间差要求，则输出 $-1$ 。

解题思路

本题要求在满足时间差约束的前提下，最小化花盆的宽度。这是一个典型的最优化问题，可以观察到其答案具有单调性：如果一个宽度为 $w$ 的花盆可以满足条件，那么任何宽度大于 $w$ 的花盆也一定能满足条件。这个性质提示我们可以使用二分答案来解决问题。

我们的目标是二分查找最小的可行宽度 $w$ 。为此，我们需要设计一个 check(w) 函数，该函数能判断给定的宽度 $w$ 是否可行。

`check(w)` 函数：判断宽度 $w$ 是否可行

宽度 $w$ 可行，当且仅当存在一个花盆的放置区间 $[x_{pos}, x_{pos} + w]$ ，使得所有被这个花盆接住的水滴中，最大和最小的下落时间之差至少为 $d$ 。

这个问题可以转化为：是否存在一个 $x$ 坐标区间 $[x_{pos}, x_{pos} + w]$ ，其中包含的所有水滴点的 $y$ 坐标最大值与最小值之差大于等于 $d$ 。

我们可以通过滑动窗口（或称“平面扫描”）的方法来高效地解决这个子问题：

将所有 $n$ 个水滴按 $x$ 坐标从小到大排序。
我们使用两个指针 left 和 right 在这个排好序的数组上移动，维护一个“窗口”。right 指针向右扩展窗口，left 指针在必要时向右收缩窗口。
窗口需要满足的条件是，其中所有点的 $x$ 坐标范围不超过我们正在检查的宽度 $w$ 。即，对于窗口中的所有点 $p_i$ ( $left \le i \le right$ )，始终保持 $p_{right}.x - p_{left}.x \le w$ 。
在维护这个滑动窗口的同时，我们需要高效地查询窗口内所有点的 $y$ 坐标的最大值和最小值。如果 max_y - min_y >= d，那么就说明宽度 $w$ 是可行的，check(w) 函数返回 true。
为了在滑动窗口中高效地查询最大/最小值，我们可以使用两个单调队列（deque）。一个单调递减队列用来维护当前窗口的最大值，一个单调递增队列用来维护当前窗口的最小值。通过这种方法，每次查询和更新窗口都只需要均摊 $\mathcal{O}(1)$ 的时间。

算法整体流程：

预排序：将所有水滴按 $x$ 坐标升序排序。这一步在所有 check 函数调用前只做一次。
二分答案：
- 设定二分范围 [low, high]，例如 [0, 1000001]。
- 在循环中，取 mid = (low + high) / 2。
- 调用 check(mid)：
  - 如果 check(mid) 返回 true，说明宽度 mid 可行，我们尝试寻找更小的宽度。记录 ans = mid，并更新 high = mid - 1。
  - 如果 check(mid) 返回 false，说明宽度 mid 太小，需要增大。更新 low = mid + 1。
输出结果：二分结束后，ans 就是最小的可行宽度。如果自始至终没有找到可行的宽度，则输出 -1。

check(w) 的时间复杂度为 $\mathcal{O}(n)$ 。二分答案需要 $\mathcal{O}(\log(\text{max_coord}))$ 次迭代。因此，总时间复杂度为 $\mathcal{O}(n \log n + n \log(\text{max_coord}))$ ，其中 $n \log n$ 来自于初始排序。这个复杂度足以通过本题。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

struct Drop {
    int x, y;
};

bool compareDrops(const Drop& a, const Drop& b) {
    return a.x < b.x;
}

bool check(long long width, int n, long long d, const std::vector<Drop>& drops) {
    if (width < 0) return false;
    std::deque<int> min_q, max_q;
    int left = 0;
    for (int right = 0; right < n; ++right) {
        while (!min_q.empty() && drops[min_q.back()].y >= drops[right].y) {
            min_q.pop_back();
        }
        min_q.push_back(right);

        while (!max_q.empty() && drops[max_q.back()].y <= drops[right].y) {
            max_q.pop_back();
        }
        max_q.push_back(right);

        while (drops[right].x - drops[left].x > width) {
            if (!min_q.empty() && min_q.front() == left) {
                min_q.pop_front();
            }
            if (!max_q.empty() && max_q.front() == left) {
                max_q.pop_front();
            }
            left++;
        }

        if (!min_q.empty() && !max_q.empty()) {
            if ((long long)drops[max_q.front()].y - drops[min_q.front()].y >= d) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long d;
    cin >> n >> d;
    vector<Drop> drops(n);
    int max_x = 0;
    for (int i = 0; i < n; ++i) {
        cin >> drops[i].x >> drops[i].y;
        max_x = max(max_x, drops[i].x);
    }

    sort(drops.begin(), drops.end(), compareDrops);

    long long low = 0, high = max_x, ans = -1;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, n, d, drops)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

class Drop implements Comparable<Drop> {
    int x, y;

    public Drop(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Drop other) {
        return Integer.compare(this.x, other.x);
    }
}

public class Main {
    private static boolean check(long width, int n, long d, Drop[] drops) {
        if (width < 0) return false;
        Deque<Integer> minQ = new LinkedList<>();
        Deque<Integer> maxQ = new LinkedList<>();
        int left = 0;
        for (int right = 0; right < n; right++) {
            while (!minQ.isEmpty() && drops[minQ.peekLast()].y >= drops[right].y) {
                minQ.pollLast();
            }
            minQ.offerLast(right);

            while (!maxQ.isEmpty() && drops[maxQ.peekLast()].y <= drops[right].y) {
                maxQ.pollLast();
            }
            maxQ.offerLast(right);

            while (drops[right].x - drops[left].x > width) {
                if (!minQ.isEmpty() && minQ.peekFirst() == left) {
                    minQ.pollFirst();
                }
                if (!maxQ.isEmpty() && maxQ.peekFirst() == left) {
                    maxQ.pollFirst();
                }
                left++;
            }

            if (!minQ.isEmpty() && !maxQ.isEmpty()) {
                if ((long)drops[maxQ.peekFirst()].y - drops[minQ.peekFirst()].y >= d) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long d = sc.nextLong();
        Drop[] drops = new Drop[n];
        int maxX = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            drops[i] = new Drop(x, y);
            maxX = Math.max(maxX, x);
        }

        Arrays.sort(drops);

        long low = 0, high = maxX, ans = -1;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (check(mid, n, d, drops)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

import sys
from collections import deque

def check(width, n, d, drops):
    if width < 0:
        return False
    
    min_q = deque()
    max_q = deque()
    left = 0
    
    for right in range(n):
        while min_q and drops[min_q[-1]][1] >= drops[right][1]:
            min_q.pop()
        min_q.append(right)
        
        while max_q and drops[max_q[-1]][1] <= drops[right][1]:
            max_q.pop()
        max_q.append(right)
        
        while drops[right][0] - drops[left][0] > width:
            if min_q and min_q[0] == left:
                min_q.popleft()
            if max_q and max_q[0] == left:
                max_q.popleft()
            left += 1
            
        if min_q and max_q:
            min_y = drops[min_q[0]][1]
            max_y = drops[max_q[0]][1]
            if max_y - min_y >= d:
                return True
                
    return False

def main():
    line = sys.stdin.readline()
    if not line.strip():
        return
    n_str, d_str = line.split()
    n = int(n_str)
    d = int(d_str)

    drops = []
    max_x = 0
    lines = sys.stdin.readlines()
    for line in lines:
        if line.strip():
            x, y = map(int, line.split())
            drops.append((x, y))
            if x > max_x:
                max_x = x
    
    drops.sort()
    
    low, high = 0, max_x
    ans = -1
    
    while low <= high:
        mid = (low + high) // 2
        if check(mid, n, d, drops):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == "__main__":
    main()

算法及复杂度

算法: 二分答案、滑动窗口、单调队列
时间复杂度: $\mathcal{O}(n \log n + n \log(\text{max_x}))$ 。预排序需要 $\mathcal{O}(n \log n)$ 。二分答案进行 $\mathcal{O}(\log(\text{max_x}))$ 次，每次 check 函数内部的滑动窗口和单调队列操作是 $\mathcal{O}(n)$ 。
空间复杂度: $\mathcal{O}(n)$ ，用于存储水滴和单调队列。