AT_abc334_c [ABC334C] Socks 2

题目描述

高桥君有 $N$ 双袜子，第 $i$ 双袜子由颜色为 $i$ 的两只袜子组成。某天，高桥君在整理抽屉时，发现颜色为 $A_1,A_2,\dots,A_K$ 的袜子各丢失了一只。因此，他决定用剩下的 $2N-K$ 只袜子，重新组合成 $\left\lfloor\frac{2N-K}{2}\right\rfloor$ 对，每对由两只袜子组成。

由颜色 $i$ 和颜色 $j$ 的袜子组成的一对袜子的“奇妙度”定义为 $|i-j|$。高桥君希望所有组合的奇妙度总和尽可能小。

请你计算，合理组合剩余袜子后，奇妙度总和的最小值是多少。注意，如果 $2N-K$ 是奇数，会有一只袜子无法组成任何一对。

输入格式

输入从标准输入读入，格式如下：

$N$ $K$ $A_1$ $A_2$ $\dots$ $A_K$

输出格式

请输出奇妙度总和的最小值。

输入输出样例 #1

输入 #1

4 2
1 3

输出 #1

2

输入输出样例 #2

输入 #2

5 1
2

输出 #2

0

输入输出样例 #3

输入 #3

8 5
1 2 4 7 8

输出 #3

2

说明/提示

限制

• $1\leq K\leq N \leq 2\times 10^5$
• $1\leq A_1 < A_2 < \dots < A_K \leq N$
• 输入均为整数

样例解释 1

以下用 $(i,j)$ 表示由颜色 $i$ 和颜色 $j$ 的袜子组成的一对。颜色 $1,2,3,4$ 的袜子分别剩下 $1,2,1,2$ 只。若组成 $(1,2),(2,3),(4,4)$ 这 $3$ 对，则奇妙度总和为 $|1-2|+|2-3|+|4-4|=2$，这是最小值。

样例解释 2

最优方案是组成 $(1,1),(3,3),(4,4),(5,5)$ 这 $4$ 对袜子，剩下颜色 $2$ 的袜子 $1$ 只无法组成一对。

由 ChatGPT 4.1 翻译