#B. 袜子

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

袜子

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

高桥君有 NN 双袜子，第 ii 双袜子的编号是 ii ，有一天他突然意识到了自己丢失了 KK 只袜子，我们定义两只袜子的 “差异度” 为这两只袜子编号的差的绝对值。

现给你这 KK 只袜子的编号，把剩余的 2N−K2N-K 只袜子两两配对，求配对后差异度和的最小值。注意到如果 KK 是奇数，配对后剩余一只袜子是允许的，且不算入差异度的计算中。

第一行输入 N,KN,K，第二行输入 KK 个数表示丢失的袜子的编号。

题目描述

高橋君は N N 組の靴下を持っており、i i 番目の組は色 i i の靴下 2 2 枚からなります。 ある日タンスの中を整理した高橋君は、色 A1,A2,…,AK A_1,A_2,\dots,A_K の靴下を 1 1 枚ずつなくしてしまったことに気づいたので、残っている 2N−K 2N-K 枚の靴下を使って、靴下 2 2 枚ずつからなる ⌊2N−K2⌋ \lfloor\frac{2N-K}{2}\rfloor 個の組を新たに作り直すことにしました。 色 i i の靴下と色 j j の靴下からなる組の奇妙さは ∣i−j∣ |i-j| として定義され、高橋君は奇妙さの総和をできるだけ小さくしたいです。

残っている靴下をうまく組み合わせて ⌊2N−K2⌋ \lfloor\frac{2N-K}{2}\rfloor 個の組を作ったとき、奇妙さの総和が最小でいくつになるか求めてください。 なお、2N−K 2N-K が奇数のとき、どの組にも含まれない靴下が 1 1 枚存在することに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K A1 A_1 A2 A_2 … \dots AK 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≤ K≤ N ≤ 2× 105 1\leq\ K\leq\ N\ \leq\ 2\times\ 10^5
  • 1≤ A1 < A2 < … < AK ≤ N 1\leq\ A_1\ <\ A_2\ <\ \dots\ <\ A_K\ \leq\ N
  • 入力は全て整数

Sample Explanation 1

以下、色 i i の靴下と色 j j の靴下からなる組を (i,j) (i,j) と表記します。 色 1,2,3,4 1,2,3,4 の靴下がそれぞれ 1,2,1,2 1,2,1,2 枚ずつあります。 (1,2),(2,3),(4,4) (1,2),(2,3),(4,4) の 3 3 組を作ると、奇妙さの総和は ∣1−2∣+∣2−3∣+∣4−4∣=2 |1-2|+|2-3|+|4-4|=2 となり、これが最小です。

Sample Explanation 2

(1,1),(3,3),(4,4),(5,5) (1,1),(3,3),(4,4),(5,5) の 4 4 組を作り、色 2 2 の靴下を 1 1 枚余らせる（どの組にも入れない）のが最適です。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 19ms
  • Powered by Hydro v4.9.27 Community