[BOJ 17522] Canal
문제
유형
- 이분탐색
- 투 포인터
풀이
풀이가 떠오르지 않아서 여러 코드를 찾아보았다.
투 포인터가 익숙하지 않아서 풀이가 잘 떠오르지 않았던 것 같다.
x좌표간의 길이가 될 수있는 0~2e9 사이의 값을 이분탐색하면서 진행한다. 기준 값을 d라고 했을 때
시작과 끝점을 0번 인덱스로 잡고 두 좌표의 x 거리가 d 이하일 때 나머지 점들의 y 좌표간 최대 거리가 d 이하인지를 계산한다.
예를 들어 N개의 전체 좌표 중 인덱스 a~b의 x좌표 최대 거리가 d일 때 미리 저장해두었던 a-1까지의 y의 최대 최소 좌표와 b+1까지의 최대 최소 좌표를 미리 저장해두면 O(1)으로 a~b의 좌표를 제외한 좌표들의 최대 최소 y좌표를 구할 수 있고 y 거리가 d이하인지를 확인할 수 있다.
만약 x, y 거리가 모두 d 이하이면 저장해두고 더 작은 d를 찾기 위해 이분탐색을 이어 나간다.
코드
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };
using namespace std;
int n;
pair<int, int> v[300001];
int frontYMax[300001];
int frontYMin[300001];
int backYMax[300001];
int backYMin[300001];
bool solve(int d) {
int s = 0, e = 0;
while (s <= e && e < n) {
if (v[e].first - v[s].first <= d) {
if (s == 0 && e == n - 1) return true;
int MaxY = -1e9, MinY = 1e9;
if (s > 0) {
MaxY = frontYMax[s - 1];
MinY = frontYMin[s - 1];
}
if (e < n - 1) {
MaxY = max(MaxY, backYMax[e + 1]);
MinY = min(MinY, backYMin[e + 1]);
}
if (MaxY - MinY <= d) return true;
e++;
}
else s++;
}
return false;
}
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i].first >> v[i].second;
sort(v, v + n);
frontYMax[0] = frontYMin[0] = v[0].second;
backYMax[n - 1] = backYMin[n - 1] = v[n - 1].second;
for (int i = 1; i < n; i++) {
frontYMax[i] = max(frontYMax[i - 1], v[i].second);
frontYMin[i] = min(frontYMin[i - 1], v[i].second);
backYMax[n - 1 - i] = max(backYMax[n - i], v[n - 1 - i].second);
backYMin[n - 1 - i] = min(backYMin[n - i], v[n - 1 - i].second);
}
long long l = 0, r = 2e9, mid;
long long ans;
while (l <= r) {
mid = (l + r) / 2;
if (solve(mid)) {
ans = mid; r = mid - 1;
}
else l = mid + 1;
}
cout << ans / 2 << '.' << (ans % 2 == 0 ? 0 : 5);
return 0;
}
Author And Source
이 문제에 관하여([BOJ 17522] Canal), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@asdsa2134/BOJ-17522-Canal저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)