302929: CF571B. Minimization

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Minimization

题意翻译

给定数组$A$ 和值$k$ ,你可以重排$A$ 中的元素,使得$\displaystyle\sum_{i=1}^{n-k} |A_i-A_{i+k}|$ 最小。输出最小值。

题目描述

You've got array $ A $ , consisting of $ n $ integers and a positive integer $ k $ . Array $ A $ is indexed by integers from $ 1 $ to $ n $ . You need to permute the array elements so that value ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF571B/74275c71e404f8e7fe1cae2f08e7a067764084b1.png) became minimal possible. In particular, it is allowed not to change order of elements at all.

输入输出格式

输入格式


The first line contains two integers $ n,k $ ( $ 2<=n<=3·10^{5} $ , $ 1<=k<=min(5000,n-1) $ ). The second line contains $ n $ integers $ A[1],A[2],...,A[n] $ ( $ -10^{9}<=A[i]<=10^{9} $ ), separate by spaces — elements of the array $ A $ .

输出格式


Print the minimum possible value of the sum described in the statement.

输入输出样例

输入样例 #1

3 2
1 2 4

输出样例 #1

1

输入样例 #2

5 2
3 -5 3 -5 3

输出样例 #2

0

输入样例 #3

6 3
4 3 4 3 2 5

输出样例 #3

3

说明

In the first test one of the optimal permutations is $ 1 4 2 $ . In the second test the initial order is optimal. In the third test one of the optimal permutations is $ 2 3 4 4 3 5 $ .

Input

题意翻译

给定数组$A$ 和值$k$ ,你可以重排$A$ 中的元素,使得$\displaystyle\sum_{i=1}^{n-k} |A_i-A_{i+k}|$ 最小。输出最小值。

加入题单

上一题 下一题 算法标签: