/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は果物農園で収穫されたりんごの箱詰め作業を担当しています。収穫された N 個のりんごを K 個の箱に分けて出荷することになりました。
それぞれのりんごには重さが測定されており、i 番目 (1 \leq i \leq N) のりんごの重さは A_i グラムです。
出荷先からは、品質管理のため以下の条件を満たす箱詰めを行うよう依頼されています：
- N 個のりんごそれぞれをちょうど 1 つの箱に入れ、どの箱にも少なくとも 1 個のりんごが入るようにする。
- 各箱について、その箱に入っているりんごの重さの最大値と最小値の差を「箱のばらつき度」と呼ぶ。りんごが 1 個だけ入っている箱のばらつき度は 0 とする。
高橋君は、K 個すべての箱のばらつき度の合計をできるだけ小さくしたいと考えています。
条件を満たすようにりんごを箱に分けるとき、すべての箱のばらつき度の合計の最小値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
1 行目には、りんごの個数を表す整数 N と箱の数を表す整数 K が、スペース区切りで与えられます。
2 行目には、各りんごの重さを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられます。
出力
すべての箱のばらつき度の合計の最小値を 1 行で出力してください。
入力例 1
5 2 3 1 4 1 5
出力例 1
2
入力例 2
8 3 10 25 12 30 15 28 11 22
出力例 2
10
入力例 3
15 4 100 250 180 300 120 275 190 310 105 260 175 295 130 280 200
出力例 3
100
Score : 366 pts
Problem Statement
Takahashi is in charge of packing apples harvested at a fruit farm into boxes. He needs to distribute N harvested apples into K boxes for shipment.
The weight of each apple has been measured, and the weight of the i-th (1 \leq i \leq N) apple is A_i grams.
The shipping destination has requested that the packing satisfy the following conditions for quality control:
- Each of the N apples must be placed into exactly 1 box, and every box must contain at least 1 apple.
- For each box, the difference between the maximum and minimum weight of the apples in that box is called the "variation" of the box. The variation of a box containing only 1 apple is 0.
Takahashi wants to minimize the total variation across all K boxes.
Given that the apples are distributed into boxes satisfying the conditions, find the minimum possible total variation across all boxes.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
The first line contains an integer N representing the number of apples and an integer K representing the number of boxes, separated by a space.
The second line contains N integers A_1, A_2, \ldots, A_N representing the weight of each apple, separated by spaces.
Output
Print the minimum possible total variation across all boxes in a single line.
Sample Input 1
5 2 3 1 4 1 5
Sample Output 1
2
Sample Input 2
8 3 10 25 12 30 15 28 11 22
Sample Output 2
10
Sample Input 3
15 4 100 250 180 300 120 275 190 310 105 260 175 295 130 280 200
Sample Output 3
100