백준 14921 용액합성하기 c++ // 이분탐색 정석패턴

https://www.acmicpc.net/problem/14921

14921번: 용액 합성하기

1.의사코드

1. v[i]를 돌면서 -v[i]의 idx를찾는다

2. 정답후보는 idx-1, idx, idx+1이다.

3. 범위쳌 / 자기자신제외 / 정답갱신

 

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ret=200000000+1;
int n;
vector<ll> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=0;i<n;++i){
		ll tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());
	//for (auto i : v) cout << i << " ";
	//cout << "\n";

	for (int i = 0; i < n; ++i) {
		ll cur = v[i];
		int idx = lower_bound(v.begin()+i+1, v.end(),-1*v[i]) - v.begin();
		for (int k = -1; k <= 1; ++k) {
			if (idx + k < 0 || idx + k >= n) continue; //범위쳌
			if (idx + k == i) continue; //자기자신제외
			if (abs(ret) > abs(cur + v[idx + k])) { //정답갱신
				ret = cur + v[idx + k];
			}
		}
	}
	cout << ret;
	return 0;
}