Hoofball

题目描述

为了准备即将到来的 hoofball 锦标赛，农夫约翰正在训练他的 $N$ 头奶牛（方便起见编号为 $1\dots N$，其中 $1 \leq N \leq 100$）进行传球练习。奶牛们都站在谷仓一侧的一条很长的直线上，第 $i$ 头奶牛站在距离谷仓 $x_i$ 的位置（$1 \leq x_i \leq 1000$）。每头奶牛的位置都互不相同。 在训练开始时，农夫约翰会把若干个球传给不同的奶牛。当第 $i$ 头奶牛接到球时（无论是从农夫约翰还是从其他奶牛那里接到），她都会把球传给离她最近的那头奶牛（如果有多头奶牛与她距离相同，则传给其中位置最靠左的那头）。 为了让所有奶牛都至少得到一点传球练习，农夫约翰希望确保每头奶牛都至少曾经持有过一次球。请你帮助他计算：为了保证这一点能够发生（假设他会把球交给合适的一组初始奶牛），他一开始最少需要分发多少个球。

输入格式

第一行输入 $N$。 第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个整数为 $x_i$。

输出格式

请输出农夫约翰最少需要最初传给奶牛的球的数量，使得每头奶牛都能至少持有过一次球。

5
7 1 3 11 4

2

提示

在上述例子中，农夫约翰应该把一个球传给位置 $x=1$ 的奶牛，并把另一个球传给位置 $x=11$ 的奶牛。$x=1$ 的奶牛会把球传给 $x=3$ 的奶牛，之后这个球会在 $x=3$ 与 $x=4$ 的奶牛之间来回传递。$x=11$ 的奶牛会把球传给 $x=7$ 的奶牛，后者会把球传给 $x=4$ 的奶牛，之后这个球也会在 $x=3$ 与 $x=4$ 的奶牛之间循环传递。这样，所有奶牛都至少会被传到一次球（可能是农夫约翰传的，也可能是其他奶牛传的）。 可以看出，不存在仅将球最初传给某一头奶牛就能使得每头奶牛最终都能接到球的情况。 题目来源：Dhruv Rohatgi

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze