分数: 350 点
问题陈述
高桥有 N 双袜子,以及 i第一双由两双彩色袜子组成 i。 有一天,高桥整理完抽屉柜后,发现自己丢失了每种颜色的一只袜子。 A_1, A_2, \dots, A_K,所以他决定使用剩余的 2N-K 袜子制作 \lfloor\frac{2N-K}{2}\rfloor 一双新袜子,每双由两只袜子组成。 的 奇怪 一双彩色袜子 i 和一只彩色袜子 j 定义为 |i-j|,高桥希望尽量减少总的奇怪现象。
找出制作时可能的最小总怪异度 \lfloor\frac{2N-K}{2}\rfloor 剩余袜子中的一双。 请注意,如果 2N-K 很奇怪,将会有一只袜子不包含在任何一双中。
约束
- 1\leq K\leq N \leq 2\times 10^5
- 1\leq A_1 < A_2 < \dots < A_K \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \dots A_K
输出
将最小总怪异度打印为整数。
示例输入 1
4 2 1 3
示例输出 1
2
下面,让 (i,j) 表示一双同色的袜子 i 和一只彩色袜子 j.
有 1, 2, 1, 2 彩色袜子 分别是 1, 2, 3, 4。 创建对 (1,2),(2,3),(4,4) 导致了完全奇怪的结果 |1-2|+|2-3|+|4-4|=2,这是最小值。
示例输入 2
5 1 2
示例输出 2
0
最佳解决方案是使配对 (1,1),(3,3),(4,4),(5,5) 并留下一只彩色袜子 2 作为盈余(不包含在任何对中)。
示例输入 3
8 5 1 2 4 7 8
示例输出 3
2