백준 2467 두용액 c++ //이분탐색 정답후보를 탐색하라

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

2467번: 용액

0. 시간복잡도

10만*10만 -> 시간초과 -> 10만*이분탐색(log10만) -> 쌉가능

 

1. 의사코드

-99 -2 -1 4 98 99 100

1. lowerbound로 99를 찾는다.

2. lower_bound 특징(99이상인 위치 리턴) 으로 인해 정답후보는 98 or 99 or 100 중 하나이다.

3. 조건 : 범위내 and 현재정답보다최적 and 자기자신은제외

4. 자기자신제외 검사 개선 : (i != nxt) 로 검사하는게 더 정확할것같다.

 

2.전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ret1=1000000000+1, ret2=1000000000+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);
	}

	for (int i = 0; i < n; ++i) {
		int idx = lower_bound(v.begin(), v.end(), -1 * v[i])-v.begin();
		//cout << idx << "\n";

		//1. idx로 자신의 역을찾는다
		//정답후보 : idx-1 or idx, idx+1
		//조건 : 범위내 & 현재정답보다 최적 & 자기자신은제외
		if (idx - 1 >= 0 && abs(v[i] + v[idx - 1]) < abs(ret1 + ret2)
			&& v[i]!=v[idx-1] && i!=idx-1) {
			ret1 = v[i];
			ret2 = v[idx - 1];
			//cout << v[i] << " " << v[idx - 1] << "\n";
		}

		if (idx <n && abs(v[i] + v[idx]) < abs(ret1 + ret2)
			&& v[i] != v[idx]) {
			ret1 = v[i];
			ret2 = v[idx];
		}

		if (idx + 1 <n && abs(v[i] + v[idx + 1]) < abs(ret1 + ret2)
			&& v[i] != v[idx + 1]) {
			ret1 = v[i];
			ret2 = v[idx + 1];
		}

	}
	cout << ret1 << " " << ret2;

	return 0;
}