7454. 最小代价配对 (Minimum Cost Pairs)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 最小代价配对 (Minimum Cost Pairs) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 给定一个包含 $n$ 个整数的数组，考虑组成 $k$ 对配对。数组中的每个元素最多只能出现在其中一个配对中，配对 $(a, b)$ 的代价定义为 $|a - b|$。一种配对方案的代价是其包含的所有配对的代价之和。 请分别计算当 $k = 1, 2, \dots, \lfloor n/2 \rfloor$ 时，最小配对代价总和。 ## 输入格式 第一行包含一个整数 $n$：数组的大小。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$：数组中的元素。 ## 输出格式 输出 $\lfloor n/2 \rfloor$ 个整数，依次对应当 $k = 1, 2, \dots, \lfloor n/2 \rfloor$ 时的最小配对代价。 ## 输入输出样例 ### 输入 #1 ```text 8 3 1 2 7 9 3 4 7 ``` ### 输出 #1 ```text 0 0 1 6 ``` ## 说明/提示 一种可能的最优配对情况如下： - $k=1$ 时配对为：$[(3,3)]$； - $k=2$ 时配对为：$[(3,3), (7,7)]$； - $k=3$ 时配对为：$[(1,2), (3,3), (7,7)]$； - $k=4$ 时配对为：$[(1,2), (3,3), (4,7), (7,9)]$。 ### 数据规模与约定 - $2 \le n \le 2 \cdot 10^5$ - $1 \le x_i \le 10^9$