https://www.acmicpc.net/problem/2212
시간 2초, 메모리 128MB

input :

• N(1 ≤ N ≤ 10,000)
• K(1 ≤ K ≤ 1000)
• N개의 센서의 좌표

output :

• 첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력

조건 :

• 고속도로 위에 최대 K개의 집중국

• 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간

• 집중국의 수신 가능 영역의 길이의 합을 최소화

• 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치

---

센서들이 N개 있고 집중국을 K개 놓을 수 있을 때 집중국의 수신 가능 영역 길이의 합을 찾으시오. 이다

K == N의 경우에는 수신가능 길이는 0이 될 것이다. 각 센서의 위치에 놓으면 되니까

그렇다면 K == 1개인 경우에는? 가장 멀리 떨어져있는 두 센서간의 거리 차가 답이 될 것이다.
그러면 하나 더 늘릴 때마다 어떻게 해야 하는가?

가장 큰 놈

가장 거리가 먼 두 센서를 찾아 그 중간을 끊어버리자.
예전에도 이와 비슷한 문제가 있었는데 행복 유치원 이라는 문제였고, 코포에서도 뭔가가 있었다.

우선순위 큐를 통해서 가장 큰 놈을 찾게 하자. 그러다가 k == n의 경우에는 반복문을 멈춘다.

예외

N, K의 범위가 서로 연관이 있는데 입력을 받을 때는 아무 상관이 없는 척 한다. 그러니까 조건이 필요하다.
조건을 걸지 않으면 IndexError가 발생할 것이다. 값이 없는데 pop을 하려고 하니까 당연한 수순이다.

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()

temp = []
ans = 0
for i in range(1, n):
    ans += data[i] - data[i - 1]
    heappush(temp, -(data[i] - data[i - 1]))

for i in range(1, k):
    if i >= n:
        break

    ans -= -heappop(temp)

print(ans)