Algorithm/백준
[백준] 2110번: 공유기 설치
youngine
2021. 2. 7. 17:07
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
#include<iostream>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
long long solution(vector<long long>&home, int m) {
int result = 0;
long long start = 0; long long end = LLONG_MAX;
while (start <= end) {
long long cnt = 1;
long long install = home[0];
long long mid = (start + end) / 2;
for (int i = 1;i < home.size();i++) {
if (mid <= home[i]-install) {
cnt++;
install = home[i];
}
}
if (m<=cnt) {
result = mid;
start = mid + 1;
}
else end = mid - 1;
}
return result;
}
int main() {
vector<long long>home;
int n, m;
cin >> n >> m;
for (int i = 0;i < n;i++) {
long long t;
cin >> t;
home.push_back(t);
}
sort(home.begin(), home.end());
cout << solution(home, m);
}