[AdditionalFile5598.zip](file://AdditionalFile5598.zip?type=additional_file)

#5598. 「USACO 2026 Second Platinum」Circle of Cows

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2026 Second Contest, Platinum Problem 1. Circle of Cows

Farmer John 在周长为 $C$ 的圆周上有 $N$（$2\le N\le 1000$）头奶牛，位于不同的位置 $l_1,\dots, l_N$（$0\le l_1 < l_2 < \dots < l_N <C, N\le C\le 10^9$）。

Farmer John 将选出 $k$ 对奶牛，其中 $1\le k\le \lfloor N/2\rfloor$，且每头奶牛最多被选中一次。他希望在选择这些对时，使得同一对中两头奶牛在圆周上的距离的最小值最大化。

对于每个 $k$ 值，帮助 Farmer John 确定最大可能的最小距离。

输入格式

第一行包含 $N$ 和 $C$。

第二行包含 $l_1\dots l_N$。

输出格式

输出一行，包含 $\lfloor N/2\rfloor$ 个空格分隔的整数，依次为 $k=1\dots \lfloor N/2\rfloor$ 的答案。

样例 1

输入

4 100
0 25 50 75

输出

50 50

对于 $k = 1$，奶牛 $1$ 可以与奶牛 $3$ 配对，它们沿圆周的距离为 $50$，使得答案为 $50$。

对于 $k = 2$，奶牛 $1$ 可以与奶牛 $3$ 配对，奶牛 $2$ 可以与奶牛 $4$ 配对，它们沿圆周的距离也为 $50$，使得答案仍然为 $50$。

样例 2

输入

4 100
0 1 2 99

输出

3 2

对于 $k = 1$，奶牛 $3$ 可以与奶牛 $4$ 配对，它们沿圆周的距离为 $2 + 100 - 99 = 3$，使得答案为 $3$。

对于 $k = 2$，奶牛 $1$ 可以与奶牛 $3$ 配对，奶牛 $2$ 可以与奶牛 $4$ 配对。这些对中的每一对包含的两头奶牛沿圆周的距离都为 $2$，使得答案为 $2$。

数据范围与提示

• 测试点 3-4：$2l_N \le C$
• 测试点 5-6：$N\le 20$
• 测试点 7-14：$N\le 100$
• 测试点 15-22：无额外约束

供题：Benjamin Qi