洛谷链接 https://www.luogu.com.cn/problem/P2698

解题思路

题目中有一个非常明显的性质，但我们先暂时不作考虑；首先可以发现，这个问题本质是一个区间最值问题。

假设我们现在拿到了一个 $W$，如何检验其是否满足要求？很简单：从头开始依次检查长度为 $W$ 的区间，即 $[0,W],[1,W+1],\dots,[\max-W,\max]$。在这里，$\max$ 为 $x$ 坐标的最大值，因为我们的区间最多只会到 $\max$。那么，一个区间 $[l,r]$ 怎样才是合法的呢？其实这本质上就是在问区间 $[l,r]$ 的最大值减去区间 $[l,r]$ 的最小值是否 $\ge D$。

• 于是，我们便得到了最暴力的检查（$\text{check}$）函数：

这个时候，我们只需要从 $0$ 到 $\max$ 去枚举花盆的长度 $i$，如果 $\text{check(i)}$ 为真，则直接输出 $i$，因为 $i$ 一定是满足条件且长度最小的答案。

• 代码如下：

遗憾的是，这份代码只能获得 $10\text{ pts}$。有许多超时的测试点，但还有三个答案错误的测试点。上面的代码时间复杂度几乎是 $\mathcal{O}(\max^3)$，而 $\max\le10^6$。先别着急，我们可以尝试把这三个答案错误而非超时的测试点更正，再考虑优化。

这里有一个不易被察觉但非常重要的错误：在同一 $x$ 坐标上，可能会有多个高度不同的水滴，即有两个水滴 $(x_i,y_i),(x_j,y_j)$ 满足 $x_i=x_j$ 且 $y_i\ne y_j$。这时候，一个坐标上的最高和最低的水滴就都有可能成为最值，不能覆盖！具体地，我们可以把 $high$ 数组也放到结构体里，存储某一 $x$ 坐标最高的水滴和最低的水滴。

• 具体实现代码如下：
• $\text{check}$ 函数也要改变：
• 于是，第二版本 $40\text{ pts}$ 的代码如下：

很好，现在我们该来优化时间复杂度了。你想到什么好点子了吗？

• 优化 $1$
• 优化 $2$

题目坑点

• 空间的限制，这导致我在模拟赛中获得了 $0$ 分；
• 记得在无解时输出 $-1$；
• 在同一个横坐标内的不同水滴需要特别注意。

完整代码