Socks 2

题目描述

Takahashi 有 $N$ 对袜子，第 $i$ 对由两只颜色为 $i$ 的袜子组成。 一天，在整理抽屉后，Takahashi 发现他丢失了颜色为 $A_1, A_2, \dots, A_K$ 的各一只袜子，因此他决定用剩下的 $2N-K$ 只袜子来制作 $\lfloor\frac{2N-K}{2}\rfloor$ 个新的袜子配对，每个配对由两只袜子组成。 一只颜色为 $i$ 的袜子与一只颜色为 $j$ 的袜子的 奇异度 定义为 $|i-j|$，Takahashi 想要使总奇异度最小。 求用剩下的袜子制作 $\lfloor\frac{2N-K}{2}\rfloor$ 个配对时可能达到的最小总奇异度。 注意如果 $2N-K$ 为奇数，会有一只袜子不被包含在任何配对中。

输入格式

输入从标准输入按如下格式给出： $N$ $K$ $A_1$ $A_2$ $\dots$ $A_K$

输出格式

输出最小的总奇异度，作为一个整数。

4 2
1 3

2

5 1
2

0

8 5
1 2 4 7 8

2

提示

$1\leq K\leq N \leq 2\times 10^5$ 1\leq A_1 < A_2 < \dots < A_K \leq N 所有输入值均为整数。下面记作 $(i,j)$ 表示一只颜色为 $i$ 的袜子与一只颜色为 $j$ 的袜子的配对。 颜色 $1,2,3,4$ 的袜子数量分别为 $1,2,1,2$。 构造配对 $(1,2),(2,3),(4,4)$ 的总奇异度为 $|1-2|+|2-3|+|4-4|=2$，这是最小值。
最优解是配对 $(1,1),(3,3),(4,4),(5,5)$ 并把一只颜色为 $2$ 的袜子作为多余（不包含在任何配对中）。

标签: AtCoder|abc334C

来源

AtCoder|abc334C