백준 2467 용액

백준 2467
백준 14921
두 문제는 거의 동일하다.

두 수의 합이 0에 가까운 두 용액을 구하는 문제이다.
a[i]+a[j]=0의 식은 a[i]=-a[j]이다.
-a[j]에 대한 lower_bound를 구한다. 구한 index에서 index-1 , index, index+1 중에 a[i]와의 합이 그나마 0에서 제일 가까운 값이다.
모든 a의 원소마다 하나씩 lower_bound를 해주고 합을 비교해서 0에서 제일 가까운 값을 찾는다.

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
int binarySearch(int t) {
	int l = 0;
	int r = v.size() - 1;

	while (l < r) {
		int m = (l + r) / 2;

		if (v[m] <t) {
			l = m + 1;
		}
		else if (v[m] >= t) {
			r = m;
		}
	}
	return l;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;

	while (n--) {
		int x;
		cin >> x;
		v.push_back(x);
	}

	sort(v.begin(), v.end());
	
	int ans1 = 1000000001;
	int ans2 = 1000000001;

	for (int i = 0; i < v.size(); i++) {
		int idx = binarySearch(-v[i]);

		if (idx < v.size() && i != idx && abs(v[i] + v[idx]) < abs(ans1 + ans2)) {
			ans1 = v[i];
			ans2 = v[idx];
		}
		if (idx-1 < v.size() && i != idx-1 && abs(v[i] + v[idx-1]) < abs(ans1 + ans2)) {
			ans1 = v[i];
			ans2 = v[idx-1];
		}
		if (idx+1 < v.size() && i != idx+1 && abs(v[i] + v[idx+1]) < abs(ans1 + ans2)) {
			ans1 = v[i];
			ans2 = v[idx+1];
		}

	}
	if (ans1 > ans2) swap(ans1, ans2);

	cout << ans1 << " " << ans2 << '\n';

}