[Link] https://www.acmicpc.net/problem/2212
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <stack>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int MAX = 5e5 + 1;
const int INF = 987654321;
int n, k;
set<int> sensors;
vector<int> svec;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for0(i, n) { int in; cin >> in; sensors.insert(in);};
if((int)sensors.size() == 1) {
cout << 0;
return 0;
}
svec.resize(sensors.size());
copy(sensors.begin(), sensors.end(), svec.begin());
sort(svec.begin(), svec.end());
vector<int> dis;
for(int i = 0; i < (int)svec.size() - 1; i++) dis.push_back(svec[i+1] - svec[i]);
sort(dis.begin(), dis.end(), greater<int>());
int erase_cnt = min(k - 1, (int)dis.size()), erase_len = 0;
for0(i, erase_cnt) erase_len+=dis[i];
cout << (svec.back() - svec.front() - erase_len);
return 0;
}