13164번: 행복 유치원

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

i번째 원생의 키를 a[i]라 하자.
a[i]-a[i-1]이 가장 작은 n-k개의 i에 대해 i-1번째 원생과 i번째 원생을 같은 조에 속하도록 만든다.

시간복잡도는 $O(n\lg n)$

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