AlgoSpot) DARPA

문제 : https://algospot.com/judge/problem/read/DARPA

카메라를 설치할때 가장 가까운 두카메라의 간격을 최대화 하는 문제입니다.

이분법과 그리디알고리즘을 이용해서 풀었습니다.

100번 반복문을 실행하는이유는 절대오차가 10^-7보다 작게하기위해서입니다.

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

int N, M; // 카메라수 중계소수
vector loc;

bool decision(double gap) {
	int install = 0;
	double min_limit = -1;

	for (int i = 0; i < loc.size(); ++i) {
		if (min_limit <= loc[i]) {
			++install;
			min_limit = loc[i] + gap;
		}
	}
	return install >= N;
}

double optimize() {
	double lo = 0; double hi = 240;

	for (int i = 0; i < 100; ++i) {
		double mid = (lo + hi) / 2.0;

		if (decision(mid)) {
			lo = mid;
		}
		else
		{
			hi = mid;
		}
	}

	return hi;
}



int main() {
	std::ios::sync_with_stdio(false);

	int C;
	cin >> C;

	while (C--) {
		cin >> N >> M;
		double pos;

		for (int i = 0; i < M; ++i) {
			cin >> pos;
			loc.push_back(pos);
		}

		cout << fixed << setprecision(2);
		cout << optimize() << endl;

		loc.clear();
	}
	return 0;
}