Sleepy Cow Herding

题目描述

农夫约翰的 $N$ 头奶牛总是跑到农场很远的地方乱逛！ 他需要你帮忙把它们赶回到一起。 农场的主牧场又长又窄——我们可以把它看作一条数轴，奶牛可以占据任意整数位置。$N$ 头奶牛当前位于互不相同的整数位置上，农夫约翰想移动它们，使它们占据连续的 $N$ 个位置（例如位置 3, 4, 5, 6, 7, 8）。 不幸的是，奶牛们很困，农夫约翰很难吸引它们的注意让它们移动。在任意时刻，他只能让一头奶牛移动，当且仅当这头奶牛是一个“端点”（即所有奶牛位置中的最小值或最大值）。当他移动一头奶牛时，他可以指示她移动到任意一个未被占据的整数位置，只要在新位置上她不再是端点即可。 注意，随着时间推移，这类移动往往会把奶牛推得越来越近。 请你确定在奶牛最终聚集到 $N$ 个连续位置之前，可能需要的最少移动次数以及可能发生的最多移动次数。

输入格式

第一行输入 $N$（$3 \leq N \leq 10^5$）。 接下来 $N$ 行，每行包含一头奶牛的位置整数，范围为 $1 \ldots 10^9$。

输出格式

第一行输出农夫约翰将奶牛聚集到一起所需的最少移动次数。 第二行输出在奶牛聚集到一起之前，他在理论上可能进行的最多移动次数。

3
7
4
9

1
2

提示

最少移动次数为 1——如果农夫约翰把位于位置 4 的奶牛移动到位置 8，那么奶牛将位于连续位置 7, 8, 9。 最多移动次数为 2。例如，位置 9 的奶牛可以移动到位置 6，然后位置 7 的奶牛可以移动到位置 5。 题目致谢：Matthew Fahrbach

标签: USACO|2019|Silver

来源

USACO|2019|Silver