2212번: 센서

https://www.acmicpc.net/problem/2212


$O(n\lg n)$
k개의 집중국을 세우면 결과적으로 k-1개의 간격은 수신 가능 영역에 포함되지 않아도 된다는 것을 알 수 있다.
따라서 전체 구간에서 큰 k-1개의 간격을 빼면 구하고자 하는 답이 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1e4;
int n, k, res, a[MAX_N];
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    res = a[n - 1] - a[0];
    for (int i = n - 1; i > 0; i--) a[i] -= a[i - 1];
    sort(a + 1, a + n);
    for (int i = 0; i < k - 1 && i < n - 1; i++) res -= a[n - 1 - i];
    printf("%d", res);
    return 0;
}