백업
시간 제한2초메모리 제한128 MB
직선 위에 정렬된 n개 회사 위치가 주어질 때, k개의 서로 겹치지 않는 쌍(2k개 회사)을 선택해 거리 합을 최소화합니다.
문제
여러 회사가 하나의 직선 도로 위에 서로 다른 위치에 있다. 정확히 k개의 네트워크 케이블을 사용해 서로 다른 2k개 회사를 k쌍으로 묶으려고 한다.
한 회사는 두 개 이상의 쌍에 포함될 수 없다. 한 쌍을 연결하는 데 필요한 케이블의 길이는 두 회사 사이의 거리와 같다.
k쌍의 케이블 길이 합이 최소가 되도록 회사를 골라 짝지을 때, 가능한 최소 총 길이를 구하라.
입력
첫 번째 줄에 회사의 수 n과 제공되는 케이블 수 k가 주어진다.
2 <= n <= 1000001 <= k <= n / 2
다음 n개의 줄에는 각 회사의 위치 s가 한 줄에 하나씩 주어진다.
0 <= s <= 1000000000- 위치는 작은 값부터 큰 값 순서로 주어진다.
- 두 회사가 같은 위치에 있는 경우는 없다.
출력
서로 다른 2k개 회사를 k쌍으로 묶을 때 필요한 케이블 길이 합의 최솟값을 하나의 정수로 출력한다.