백준2473 세 용액

작성일 | In

문제 링크

  • http://icpc.me/2473

문제 출처

  • 2010 전국 본선 고등1

사용 알고리즘

  • Parametric Search

시간복잡도

  • O(n2 log n)

풀이

N이 5000이므로 N2이나, 뒤에 로그가 딸려오는 수준으로 구현해야 하고, 둘 다 가능합니다. 전자는 슬라이딩 윈도우, 후자는 파라메트릭 서치로 구현이 가능합니다. 이 글에서는 후자의 방법을 설명합니다.

N2으로 두 개의 용액을 선택합니다. 두 용액의 특성값의 합을 t라고 한다면, 선택된 두 용액을 제외한 N-2개의 용액에서 -t와 가까운 용액을 찾습니다. (lower_bound 혹은 upper_bound) 이 작업은 log N만에 가능합니다. 혹시 모르니 ±2 정도의 범위까지 탐색을 해줍시다.
위 방법으로 O(N2 log N)만에 해결 가능합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
vector<ll> v;

struct asdf{
	ll a, b, c;
	bool operator < (asdf rhs){
		ll t1 = a + b + c;
		ll t2 = rhs.a + rhs.b + rhs.c;
		t1 = abs(t1), t2 = abs(t2);
		return t1 < t2;
	}
	asdf(){a = b = c = 0;}
	asdf(ll x, ll y, ll z) : a(x), b(y), c(z) {}
	void print(){
		ll mini = min({a, b, c});
		ll maxi = max({a, b, c});
		ll mid = a + b + c - maxi - mini;
		cout << mini << " " << mid << " " << maxi;
	}
};

void update(int i, int j, int k, asdf &ans){
	if(j < k && k < v.size()){
		asdf tmp = {v[i], v[j], v[k]};
		if(tmp < ans) ans = tmp;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];
	sort(v.begin(), v.end());
	asdf ans = {v[0], v[1], v[2]};
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			ll t = -(v[i] + v[j]);
			int idx = lower_bound(v.begin()+j+1, v.end(), t) - v.begin();
			for(int k=idx-2; k<=idx+2; k++) update(i, j, k, ans);
		}
	}
	ans.print();
}