중복 좌표가 있을 수 있으므로, STL set을 사용했다.
수신기 수 만큼, 가장 적은 수신 가능 영역을 가지는 위치를 뽑아낸다.
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 | #include <stdio.h> #include <algorithm> #include <set> using namespace std; int camera[10001]; int main(void) { int T; setbuf(stdout, NULL); scanf("%d" , &T); for (int test_case = 1; test_case <= T; test_case++) { multiset<int> s; int n,k; scanf("%d", &n); scanf("%d", &k); for (int i = 0; i < n; i++) { scanf("%d", &camera[i]); } sort(camera, camera + n);//좌표순 정렬 int answer = 0; for (int i = 0; i < n-1; i++) { s.insert(camera[i + 1] - camera[i]); } int size = s.size(); auto it = s.begin(); for (int i=0;i<size - (k-1);i++) { answer += (*it); it++; } printf("#%d %d\n", test_case, answer); } return 0; } | cs |