Casework

分类讨论（Casework）

将问题拆分为多个情况，分别针对每种情况求解。

分类讨论类问题是指可将其拆分为不同情况，且每种情况可单独求解的问题。

这类问题通常需要列出大量情况，并针对每种情况进行观察分析。

我们可以尝试寻找不同情况之间的相似性，以便用相同的方法解决多种情况。

昏昏欲睡的牧牛（Sleepy Cow Herding）

青铜级 - 中等难度

http://oj.oldmoon.cn/p/U1819FB1

我们分别求解最少移动次数和最多移动次数。我们将奶牛的位置称为“元素”，若两个元素之间没有其他元素，则称这两个元素“相邻”。

最少移动次数

最少移动次数存在三种情况：

1. 三个元素已经是连续的。

2. 存在两个相邻元素，且这两个元素之间恰好有一个空位。

3. 不满足上述两种情况的其他任何情况。

对于第一种情况，答案为$0$，因为元素本身已经连续。

对于第二种情况，答案为$1$，因为只需将孤立的元素移入另外两个元素之间的空位即可。

对于第三种情况，结果为$2$，因为在其他任何测试场景中，最优解法是要么将最小元素移至$\text{max}-2$的位置，要么将最大元素移至$\text{min}+2$的位置，之后问题就会转化为第二种情况。

最多移动次数

最多移动次数始终是有限的，因为每次操作都会使两个端点之间的距离（我们称之为“跨度”）至少减少$1$。

要最大化移动次数，最佳策略是将每个元素放置在尽可能靠近某个端点的位置（但不留在端点上）。一次移动后，跨度将等于两个相邻元素之间的最大距离，此后每一次移动都会使跨度减少$1$，直到跨度变为$2$。

因此，最多移动次数等于两个相邻元素之间的最大距离减$1$。

题目