문제
https://www.acmicpc.net/problem/17976
문제해설
n개의 선분이 있고 선분은 시작위치와 길이가 주어진다.
n개의 선분에 점을 찍을건데
점들 사이의 거리 최소값이 최대가 되도록 점을 찍어야 한다.
그 최대값을 출력해주면 된다.
문제풀이
우선 생각의 전환이 필요하다.
최소값의 최대를 구한다는 것은
최소값을 가장 크게 만들어야 한다는 것이다.
그렇다면 이제 다음 질문으로 바꿀 수 있다.
점들 사이의 최소값이 x이상 될 수 있는가?
그럼 최소값이 1이상 될 수 있는가? yes
최소값이 2이상 될 수 있는가? yes
최소값이 3이상 될 수 있는가? yes
최소값이 4이상 될 수 있는가? yes
최소값이 5이상 될 수 있는가? no
이렇게 된다면 정답은 4인 것이다.
위의 방법처럼 1부터 하나씩 늘려가며 탐색하면 좋겠지만
그렇게하면 1억번을 탐색해야하니 분명 시간초과가 발생할 것이다.
그래서 이분탐색을 사용해야 하는 것이다.
이분탐색을 사용하여 최적화 문제를 결정문제로 바꿔 해결하는 것을
Parametric Search라고 한다.
점을 찍기전에 선분들을 시작점을 기준으로 정렬할지
끝점을 기준으로 정렬할지 고민할수도 있지만
선분이 다른 선분을 포함하는 경우는 없다고 했기 때문에
그냥 편한대로 잡고 정렬해주면 된다.
그렇다면 이제 어디에 점을 찍어야 할까?
점을 왼쪽끝에 찍어야할지 오른쪽끝에 찍어야할지 생각해보자
점은 왼쪽끝에 찍어야한다.
왜냐하면 왼쪽끝에 찍는 것이 그 다음 점을 찍는데도 방해가 안되고
왼쪽끝에 찍어서 최소값에 영향을 주는 것도 없기 때문이다.
1
2
3
4
5
6
7
8
9
10
11
ll left = 0, right = (int)2e9 + 1, res = 0;
while (left <= right) {
ll mid = (right + left) / 2;
ll tmp = calculate(mid);
if (!calculate(mid))
right = mid - 1;
else {
res = max(mid, res);
left = mid + 1;
}
}
위의 코드로 이분탐색을 하며 점을 찍고
해당 값으로 점을 찍을 수 없다면 right을 mid-1로 설정한다.
해당 값으로 점을 찍을 수 있다면 left를 mid+1로 설정한다.
점을 찍는 것은 calculate() 함수에서 수행한다.
전체코드
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits.h>
using namespace std;
typedef long long ll;
int n;
struct line {
ll x1, x2, pt;
};
vector<line>arr;
bool cmp(struct line& a, struct line& b) {
if (a.x1 < b.x1)
return true;
else
return false;
}
bool calculate(int dis) {
arr[0].pt = arr[0].x1;
for (int i = 1; i < n; i++) {
if (arr[i - 1].pt + dis > arr[i].x2)
return false;
else if (arr[i - 1].pt + dis <= arr[i].x1)
arr[i].pt = arr[i].x1;
else if (arr[i - 1].pt + dis > arr[i].x1)
arr[i].pt = arr[i - 1].pt + dis;
}
return true;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
arr.push_back({ x, x + y, 0 });
}
sort(arr.begin(), arr.end(), cmp);
ll left = 0, right = (int)2e9 + 1, res = 0;
while (left <= right) {
ll mid = (right + left) / 2;
ll tmp = calculate(mid);
if (!calculate(mid))
right = mid - 1;
else {
res = max(mid, res);
left = mid + 1;
}
}
cout << res;
return 0;
}