[백준/BOJ] 백준 17976번 : Thread Knots

www.acmicpc.net/problem/17976

17976번: Thread Knots

이분 탐색, 파라메트릭 서치, 결정 문제로 mid가 가장 가까운 두 매듭 사이의 거리가 될 수 있는지 확인하여 가장 가까운 두 매듭 사이의 거리가 최대인 정수를 구한다.

 

코드

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

int n;
vector<pair<int, int>> t;

//모든 매듭 사이의 거리가 gap 이상인게 가능한지 확인
bool Decision(int gap)
{
	int limit = t[0].first;

	for (int i = 1; i < t.size(); i++)
	{
		if (limit + gap > t[i].second)
			return false;

		else
		{
			if (limit + gap > t[i].first)
				limit = limit + gap;
			else
				limit = t[i].first;
		}
	}

	return true;
}

int Solve()
{
	int left = 0;
	int right = 2000000000;
	int mid;
	int result;

	//이분 탐색
	while (left <= right)
	{
		mid = ((long long)left + (long long)right) / 2;

		//mid가 가장 가까운 두 매듭 사이의 거리가 될 수 있는지 확인
		if (Decision(mid))
		{
			result = mid;
			left = mid + 1;
		}

		else
			right = mid - 1;
	}

	return result;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int x, l;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> x >> l;
		t.push_back(make_pair(x, x + l));
	}
	sort(t.begin(), t.end());

	cout << Solve();

	return 0;
}