Minimum Cost Pairs

题目描述

给定一个包含 $n$ 个整数的数组，考虑配对 $k$ 对。每个数字最多出现在一个配对中，配对 $(a,b)$ 的代价为 |a-b|。一个配对的代价是所有配对代价的和。 计算当 $k=1,2,\dots,\lfloor n/2 \rfloor$ 时的最小配对代价。

输入格式

第一行有一个整数：数组大小。 下一行有 $n$ 个整数 $x_1,x_2,\dots,x_n$：数组内容。

输出格式

输出 $\lfloor n/2 \rfloor$ 个整数：最小配对代价。

8
3 1 2 7 9 3 4 7

0 0 1 6

提示

$2 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ 样例解释：可能的最小代价配对为 [(3,3)], [(3,3),(7,7)], [(1,2),(3,3),(7,7)] 和 [(1,2),(3,3),(4,7),(7,9)]。

标签: CSES3402|附加题2

来源

CSES3402|附加题2