帮我完成洛谷上名字是[USACO13NOV]Crowded Cows S的题

题目描述

农夫约翰一直在观察他的奶牛们。他注意到，如果在牛群中有太多的牛靠得太近，就会导致不健康的行为和情感问题。

约翰想知道他的牛群是否存在这个问题。他定义这个问题为：在一个固定长度的路段上，如果有两头高度大于等于 $y$ 的奶牛之间的距离小于 $x$，则牛群中就存在一个挤得太近的情况。

约翰有 $N$ 头牛 ($1 \leq N \leq 50,000$)，每头牛的高度为 $h_i$ ($1 \leq h_i \leq 1,000,000$)。他想知道是否存在一对牛，使得它们之间的距离小于 $x$，且它们的高度都大于等于 $y$。

输入格式

第一行包含三个整数 $N, L, R$，分别表示牛的数量，路段长度，和问题的最大高度。

接下来 $N$ 行，每行一个整数 $h_i$，表示每头牛的高度。

输出格式

如果存在一对牛，它们之间的距离小于 $x$，且它们的高度都大于等于 $y$，则输出 $1$，否则输出 $0$。

输入样例1

4 6 4
4
4
5
7

输出样例1

1

输入样例2

5 3 3
1
5
5
5
5

输出样例2

0

提示

对于 $30\%$ 的数据，$N \leq 500$。

对于 $100\%$ 的数据，$1 \leq N \leq 50,000$，$1 \leq L \leq 1,000,000$，且 $L \leq R$。

数据范围

时间限制：1.0s，空间限制：256MB

算法1

(暴力枚举) $O(n^2)$

首先对输入的牛的高度进行排序，之后枚举每头牛，再枚举它后面的每头牛，如果两头牛的高度均大于等于 $y$，且它们之间的距离小于 $x$，则输出 $1$。如果最后仍然没有满足条件的牛，则输出 $0$。

时间复杂度

暴力枚举，时间复杂度为 $O(n^2)$，无法通过此题。

算法2

(滑动窗口) $O(n \log n)$

为了方便后续操作，我们将所有的牛按照它们的高度从小到大排序。之后，我们维护一个长度为 $L$ 的滑动窗口，它的右端点与左端点之间的距离小于 $x$。我们从左到右扫描每头牛，将它加入滑动窗口的左端点，同时将滑动窗口右移，直到滑动窗口的右端点与左端点之间的距离小于 $x$。

在处理完一头牛之后，我们需要判断滑动窗口中是否存在一对牛，它们的高度均大于等于 $y$，且它们之间的距离小于 $x$。我们可以用双指针来实现这个操作。我们从滑动窗口的左端点开始，向右移动一个指针 $i$，同时向右移动一个指针 $j$，直到 $h_j - h_i \leq x$。在这个过程中，我们需要判断 $h_i$ 和 $h_j$ 是否均大于等于 $y$。如果存在一对牛满足条件，则输出 $1$。如果最后仍然没有满足条件的牛，则输出 $0$。

时间复杂度

因为需要对所有的牛进行排序，所以时间复杂度为 $O(n \log n)$。

C++ 代码

算法3

(暴力优化) $O(n \log n)$

首先对输入的牛的高度进行排序，之后枚举每头牛。如果当前牛的高度小于 $y$，则跳过这头牛。否则，我们从它的左边和右边各扩展出一个长度为 $x$ 的区间。如果这两个区间内的牛的数量均大于等于 $2$，且这两个区间中任意两头牛的高度均大于等于 $y$，则输出 $1$。

时间复杂度

因为需要对所有的牛进行排序，所以时间复杂度为 $O(n \log n)$。

C++ 代码