알고리즘/Baekjoon
이분탐색. [2467]
jdaemanv2
2023. 8. 24. 22:59
[1. 문제 설명]
https://www.acmicpc.net/problem/2467
[2. 풀이 접근]
용액을 하나 정한다.
전체에 대해서, 이 용액과 더해서 그 합이 0에 가장 가까워 지는 용액을 이분 탐색으로 찾는다.
용액들이 이미 정렬 된 상태이므로, 이분 탐색 시 두 용액의 합이
- 0보다 작다면
# 양수 용액을 더해서 0으로 만들 수 있다.
# 따라서 다음 탐색 구간을 (mid ~ hi] 구간을 잡아야 한다. - 0보다 크다면
# 음수 용액을 더해서 0으로 만들 수 있다.
# 따라서 다음 탐색 구간을 [lo ~ mid) 구간을 잡아야 한다.
[3. 코드]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <algorithm> | |
int N; | |
int liquids[100000]; | |
int find(const int v, int lo, int hi) | |
{ | |
int ret = -1; | |
int minValue = int(2e+9); | |
while (lo <= hi) { | |
const int mid = (lo + hi) / 2; | |
int value = v + liquids[mid]; | |
if (std::abs(value) < minValue) { | |
minValue = std::abs(value); | |
ret = mid; | |
} | |
if (value < 0) { | |
lo = mid+1; | |
} else { | |
hi = mid-1; | |
} | |
} | |
return ret; | |
} | |
void solve() | |
{ | |
int lo=0, hi=N-1; | |
int minValue = int(2e+9); | |
int v1 = 0, v2 = 0; | |
for (int s=0; s<N-1; s++) { | |
const int minIndex = find(liquids[s], s+1, N-1); | |
const int value = std::abs(liquids[s] + liquids[minIndex]); | |
if (value < minValue) { | |
minValue = value; | |
v1 = liquids[s]; | |
v2 = liquids[minIndex]; | |
} | |
} | |
std::cout << v1 << " " << v2 << "\n"; | |
} | |
int main() | |
{ | |
std::ios_base::sync_with_stdio(false); | |
std::cin.tie(nullptr); std::cout.tie(nullptr); | |
std::cin >> N; | |
for (int i=0; i<N; i++) { | |
std::cin >> liquids[i]; | |
} | |
solve(); | |
return 0; | |
} |