알고리즘/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. 코드]

#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;
}
view raw 2467.cpp hosted with ❤ by GitHub