问题 3259 --袜子（sock）

3259: 袜子（sock）

时间限制: 1 Sec  内存限制: 256 MB
提交: 2  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

高桥君有 N 双袜子，第 i 双由两枚颜色为 i 的袜子组成。某天整理衣柜时，高桥 君发现自己丢失了颜色为 A1, A2, . . . , AK 的袜子各一枚，于是他决定用剩下的 2N − K 枚袜子重新组成 ⌊ （2N−K）2 /2⌋ 双袜子。由颜色为 i 和 j 的袜子组成的双袜子的奇异度定义为 |i − j|，高桥君希望使奇异度的总和尽可能小。 请计算在最优组合下，奇异度的最小总和是多少。注意，如果 2N − K 是奇数，会 有一枚袜子不被包含在任何双袜子中。

输入

输入从标准输入按以下格式给出： N K A1 A2 . . . AK 

输出

输出奇异度的最小总和，以整数形式表示。

样例输入

样例1
4 2
1 3
样例2
5 1
2
样例3
8 5
1 2 4 7 8

样例输出

样例1
2
样例2
0
样例3
2

提示


【样例 1 解释】 



以下用 (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，
这是最小的可能值。 



【样例 2 输出】 



最优解是组成双袜子 (1, 1)、(3, 3)、(4, 4) 和 (5, 5)，并将颜色 2 的一枚袜子单独留下
（不包含在任何双袜子中）。



数据约束和子任务 



1 ≤ K ≤ N ≤ 2 × 10^5, 1 ≤ A1 < A2 < · · · < AK ≤ N 



输入均为整数 

来源

普及组模拟测试第五套第2题 

[提交][状态]