#abc334c. C - Socks 2

C - Socks 2

Score : 350350 points

问题描述

高桥有NN对袜子,其中第ii对包含两只颜色为ii的袜子。有一天,在整理他的抽屉后,高桥发现他丢失了颜色分别为A1,A2,,AKA_1, A_2, \dots, A_K的各一只袜子,因此他决定用剩下的2NK2N-K只袜子来制作2NK2\lfloor\frac{2N-K}{2}\rfloor对新的袜子,每对包含两只袜子。定义一双由颜色ii和颜色jj的袜子组成的袜子对的奇怪度ij|i-j|,高桥希望尽量减少总奇怪度。

求在用剩下的袜子制作2NK2\lfloor\frac{2N-K}{2}\rfloor对时,可能达到的最小总奇怪度。注意,如果2NK2N-K是奇数,则会有一只袜子未被包括在任何一对中。

以上为通义千问 qwen-max 翻译,仅供参考。

Problem Statement

Takahashi has NN pairs of socks, and the ii-th pair consists of two socks of color ii. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A1,A2,,AKA_1, A_2, \dots, A_K, so he decided to use the remaining 2NK2N-K socks to make 2NK2\lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color ii and a sock of color jj is defined as ij|i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making 2NK2\lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2NK2N-K is odd, there will be one sock that is not included in any pair.

Constraints

  • 1KN2×1051\leq K\leq N \leq 2\times 10^5
  • 1A1<A2<<AKN1\leq A_1 < A_2 < \dots < A_K \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

NN KK

A1A_1 A2A_2 \dots AKA_K

Output

Print the minimum total weirdness as an integer.

Sample Input 1

4 2
1 3

Sample Output 1

2

Below, let (i,j)(i,j) denote a pair of a sock of color ii and a sock of color jj.

There are 1,2,1,21, 2, 1, 2 socks of colors 1,2,3,41, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4)(1,2),(2,3),(4,4) results in a total weirdness of 12+23+44=2|1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

0

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5)(1,1),(3,3),(4,4),(5,5) and leave one sock of color 22 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

2

update @ 2024/3/10 01:21:12