휴게소 세우기

휴게소간의 거리를 뽑아서 정렬해서 세워 놓았다고 생각해보자.

ex)

-

----

------

---------

-----------

 

여기서 휴개소 5개를 세우려면 간격을 세로로 잘랐을 때 꼬다리가 5개가 추가로 생성되면 된다. (전형적인 이분탐색 문제)

 

 

<코드>

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N,M,L;
int road[60];
vector<int> v;

int sol(int mid){
	int n = 0;
	for(int i = 1; i < v.size(); i++){
		n += (v[i] - v[i-1] - 1) / mid;
	}
	return n;
}
int main() {
	cin>>N>>M>>L;
	v.push_back(0);v.push_back(L);
	for(int i = 0,a;i < N; i++) {cin>>a;v.push_back(a);};
	sort(v.begin(),v.end());

	int s = 1, e = L, mid = 0;
	while(s<=e){
		mid = (s+e)/2;
		if(sol(mid) > M) s = mid + 1;
		else  {
			e = mid -1;
		}
	}
	cout<<s;
	return 0;
}