백준9007 카누 선수

작성일 | In

문제 링크

  • http://icpc.me/9007

문제 출처

  • 2012 ACM-ICPC 대전 인터넷 예선 B번

사용 알고리즘

  • Parametric Search

시간복잡도

  • O(n2 log n2)

풀이

이 문제는 n이 최대 1000이기 때문에 O(n4)이나 O(n3)으로는 풀리지 않습니다. 탐색 횟수를 줄이는 것이 이 문제 해결의 요점입니다.

4개의 반에서 한 명씩 뽑아 4명의 몸무게의 합이 k에 가장 가까우면 정답이 되는 문제입니다. 4중 for문을 이용하면 O(n4)으로 답을 구할 수 있겠지만 위헤서 언급했듯이 시간초과가 납니다. 다른 방법을 찾아봅시다.
O(n2)만에 2개의 반에서 가능한 모든 합을 구할 수 있습니다. 이를 이용해 1 / 2반에서 가능한 모든 합, 그리고 3 / 4반에서 가능한 모든 합을 구한 뒤, 각각 정렬해줍니다.
이렇게 전처리를 해준 뒤, 1 / 2반의 합을 저장한 배열의 원소를 순회해줍시다. 1 / 2반 배열을 순회하면서 3 / 4반의 합을 저장한 배열에서는 이진 탐색을 이용해 가장 k와 가까운 값을 찾아서 출력을 해주면 됩니다.

전체 코드

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
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

inline bool can(int idx, int n){
	return 0<=idx && idx<n;
}

void solve(){
	int k, n; cin >> k >> n;
	vector<ll> tmp1(n), tmp2(n);
	vector<ll> a, b;
	for(int i=0; i<n; i++) cin >> tmp1[i];
	for(int i=0; i<n; i++) cin >> tmp2[i];
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) a.push_back(tmp1[i] + tmp2[j]);
	for(int i=0; i<n; i++) cin >> tmp1[i];
	for(int i=0; i<n; i++) cin >> tmp2[i];
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) b.push_back(tmp1[i] + tmp2[j]);
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	ll ans = a[0]+b[0];
	for(int i=0; i<a.size(); i++){
		ll key = a[i] - k;
		int idx1 = lower_bound(b.begin(), b.end(), abs(key)) - b.begin();
		int idx2 = idx1-1;

		if(can(idx1, b.size())){
			ll minus = abs(k-ans);
			ll t = abs(k-(a[i] + b[idx1]));
			if(minus > t) ans = a[i] + b[idx1];
			if(minus == t) ans = min(ans, a[i] + b[idx1]);
		}

		if(can(idx2, b.size())){
			ll minus = abs(k-ans);
			ll t = abs(k-(a[i] + b[idx2]));
			if(minus > t) ans = a[i] + b[idx2];
			if(minus == t) ans = min(ans, a[i] + b[idx2]);
		}
	}

	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--){
		solve();
	}
}