중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터

A. [11053] 가장 긴 증가하는 부분 수열 (Silver II)

\( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면,

\( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다.

초기값은 \( DP_{i} = 1 \)이고, 문제의 답은 \( \max_{1 \le i \le N} DP_{i} \)입니다.

int arr[1020], dp[1020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		dp[i] = 1;
		for (int j = 1; j <= i; j++){
			if (arr[j] >= arr[i]){ continue; }
			dp[i] = max(dp[i], dp[j]+1);
		}
	}
	cout << *max_element(dp+1, dp+n+1);
}

B. [2003] 수들의 합 2 (Silver III)

두 포인터 p1과 p2를 놓고, [p1, p2) 구간의 합을 저장하면서 포인터를 잘 움직여봅시다.

 

만약 현재 합이 \( M \) 이하라면 p2를 오른쪽으로 옮겨줘야 하고,

그렇지 않으면 p1을 오른쪽으로 옮겨줘야 합니다.

 

문제의 답은 합이 정확히 \( M \)이 된 횟수이며, 시간복잡도는 \( O(N) \)입니다.

 

+ \( A_{i} \)가 자연수이기 때문에 가능합니다. 그냥 정수라면 사용할 수 없습니다.

 

1. [1920] 수 찾기 (Silver IV)

수열 \( A \)와 찾는 수 \( X \)가 주어질 때, 이를 이진 탐색으로 찾아주면 됩니다.

lower_bound를 사용한다면 \( X \) 이상인 위치를 찾아줄테니, 그 위치에 있는 수가 \( X \)인지 확인해주면 됩니다.

 

주의할 점: \( X \)가 수열의 모든 원소보다 크다면 lower_bound가 \( N+1 \)번 위치를 가리키게 됩니다.

근데 이걸 생각 못한 채로 그냥 Indexing을 해도 웬만해서는 답이 잘 나오지만...

[-6, -4, -2]에서 0을 찾으려 하는 순간 잘못된 답이 나오는 걸 볼 수 있습니다.

int arr[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	int q; cin >> q; while (q--){
		int x; cin >> x;
		auto idx = lower_bound(arr+1, arr+n+1, x) - arr;
		if (idx > n){ cout << 0 << endl; continue; }
		cout << (arr[idx] == x) << endl;
	}
}

STL이 존재하는데에는 이유가 있습니다. 신나게 set을 박아주면 됩니다.

set<int> s;

void Main(){
	int n; cin >> n;
	while (n--){ int x; cin >> x; s.insert(x); }
	int q; cin >> q;
	while (q--){ int x; cin >> x; cout << s.count(x) << endl; }
}

 

2. [1654] 랜선 자르기 (Silver III)

문제의 답이 \( X \)라고 하면, \( X \) 이하의 길이를 가지는 랜선은 만들 수 있지만, \( X \) 초과의 길이를 가지는 랜선은 만들 수 없기에, 이 문제를 파라메트릭 서치로 풀 수 있는 길을 만들어줍니다.

 

그러니, 길이가 \( x \)인 랜선을 \( N \)개 이상 만들 수 있는지 판별하는 함수를 만들어봅시다.

어떤 랜선 \( a \)에 대해, 길이가 \( x \)인 랜선은 \( \lfloor a/x \rfloor \)개 만들 수 있습니다.

그러니, 랜선의 배열을 \( A \)라고 하면 길이가 \( x \)인 랜선은 \( \sum_{i=1}^{K} \lfloor A_{i}/x \rfloor \)개 만들 수 있습니다.

이 값이 \( N \) 이상이라면 더 긴 길이를 시도해보고, 그렇지 않다면 더 짧은 길이를 시도해보면 됩니다.

int arr[10020];

void Main(){
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll st = 1, ed = 1e10, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += arr[i] / mid; }
		if (res >= k){ st = mid+1; ans = mid; } else{ ed = mid-1; }
	}
	cout << ans;
}

3. [12015] 가장 긴 증가하는 부분 수열 2 (Gold II)

A. [11053] 가장 긴 증가하는 부분 수열 의 점화식을 그대로 가지고 올 수는 없는 문제입니다.

 

그러니, DP를 참신하게 세워봅시다.

\( DP_{i} := \) 길이가 \( i \)인 LIS의 마지막 원소 중 최솟값

도대체 이걸로 뭘 하나 싶겠지만, 이러면 \( DP_{i} < DP_{i+1} \)이라는 재밌는 사실이 하나 나오게 됩니다.

 

그리고 저 사실이 큰 역할을 해줍니다.

\( DP_{k} < A_{i} \)인 가장 큰 \( k \)를 찾았다면, 이는 길이 \( k+1 \)의 LIS를 만들 수 있다는 것이며, 더 나아가 길이 \( k+2 \)의 LIS는 만들 수 없다는 소리가 되기 때문입니다.

그러니, \( DP_{k} < A_{i} \)인 가장 큰 \( k \)를 찾은 뒤, \( DP_{k+1} \)을 이에 맞게 업데이트해주면 됩니다.

만약 길이 \( k+1 \)의 LIS가 없었다면, 답의 길이도 1 증가시켜야 합니다.

 

실제 구현에서는 구현의 편의를 위해 \( DP_{k} \ge A_{i} \)인 가장 작은 \( k \)를 찾은 뒤 \( DP_{k} \)를 업데이트해줍니다. 이게 위 방식과 동일함은 \( DP_{k-1} < A_{i} \le DP_{k} \)를 생각해보면 자명합니다.

int arr[1000020], lis[1000020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
		if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
	}
	cout << cnt;
}

4. [10816] 숫자 카드 2 (Silver IV)

"1. [1920] 수 찾기" 문제의 강화판입니다.

이제는 개수를 세야 하는데, 개수는 upper_bound의 위치 - lower_bound의 위치 로 구할 수 있습니다.

 

+ equal_range는 lower_bound와 upper_bound의 위치를 동시에 return합니다.

이름이 equal_range인 이유는, [lower, upper) 구간에 target과 동일한 값이 들어있기 때문입니다.

int arr[500020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	int q; cin >> q; while (q--){
		int x; cin >> x;
		auto p = equal_range(arr+1, arr+n+1, x);
		cout << p.sc - p.fr << ' ';
	}
}

"1. [1920] 수 찾기"에서 set을 박은 걸 기억하나요?

여기서는 { x: count }의 형태로 map을 박으면 됩니다.

map<int, int> mp;

void Main(){
	int n; cin >> n;
	while (n--){ int x; cin >> x; mp[x] += 1; }
	int q; cin >> q;
	while (q--){ int x; cin >> x; cout << mp[x] << ' '; }
}

5. [3020] 개똥벌레 (Gold V)

밑에서 올라오는 장애물과 위에서 내려오는 장애물을 따로 처리해봅시다.

높이 \( h \)에서 날아갈 때 부딪히는 장애물은 밑에서 올라오는 장애물 중 \( h \) 위로 올라가는 장애물의 개수 + 위에서 내려오는 장애물 중 \( h \) 밑으로 내려가는 장애물의 개수 가 됩니다.

이 2개 모두 이진 탐색을 사용하여 구해줄 수 있습니다.

 

이를 모든 높이에서 돌려준 뒤, 파괴해야 하는 장애물의 최솟값과 위치를 출력해주면 됩니다.

 

시간복잡도는 \( O(N + H \log N) \)입니다.

vector<int> v1, v2;

void Main(){
	int n, m; cin >> m >> n;
	for (int i = 1; i <= m; i++){
		int x; cin >> x;
		if (i&1){ v1.push_back(x); }
		else{ v2.push_back(n-x+1); }
	}
	sort(all(v1)); sort(all(v2));
	int ans = 1e9, cnt = 0;
	for (int i = 1; i <= n; i++){
		int c1 = v1.end() - lower_bound(all(v1), i);
		int c2 = upper_bound(all(v2), i) - v2.begin();
		int res = c1+c2;
		if (ans > res){ ans = res; cnt = 0; }
		if (ans == res){ cnt += 1; }
	}
	cout << ans << ' ' << cnt << endl;
}

(풀이 1에서 이어집니다.)

그런데 굳이 이진 탐색을 써야 할까요?

누적합을 사용해서 위에서 나온 2개의 경우를 계산해둘 수도 있다.

이제 시간복잡도는 \( O(N + H) \)가 되었습니다.

int c1[500020], c2[500020];

void Main(){
	int n, m; cin >> m >> n;
	for (int i = 1; i <= m; i++){
		int x; cin >> x;
		if (i&1){ c1[x] += 1; }
		else{ c2[n-x+1] += 1; }
	}
	for (int i = n; i >= 1; i--){ c1[i] += c1[i+1]; }
	for (int i = 1; i <= n; i++){ c2[i] += c2[i-1]; }
	int ans = 1e9, cnt = 0;
	for (int i = 1; i <= n; i++){
		int res = c1[i] + c2[i];
		if (ans > res){ ans = res; cnt = 0; }
		if (ans == res){ cnt += 1; }
	}
	cout << ans << ' ' << cnt << endl;
}

사실 누적합을 이렇게 써서 풀 수도 있습니다.

밑에서 올라오는 건 [1, h] 구간에 장애물이 생기는 거고, 위에서 내려오는 건 [h, H] 구간에 장애물이 생기는 것이 됩니다.

그리고 [st, ed] 구간의 장애물은 \( A_{st} \)에 1을 더한 뒤 \( A_{ed+1} \)에 1을 빼고, 나중에 누적합을 넣는 방식으로 구현할 수 있습니다.

시간복잡도는 \( O(N + H) \)가 됩니다.

int prf[500020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int pos; cin >> pos;
		if (i&1){ prf[1] += 1; prf[pos+1] -= 1; }
		else{ prf[m-pos+1] += 1; prf[m+1] -= 1; }
	}
	for (int i = 1; i <= m; i++){ prf[i] += prf[i-1]; }
	int mn = 1e9, mnc = 0;
	for (int i = 1; i <= m; i++){
		if (mn > prf[i]){ mn = prf[i]; mnc = 0; }
		if (mn == prf[i]){ mnc += 1; }
	}
	cout << mn << ' ' << mnc;
}

6. [2792] 보석 상자 (Silver II)

질투심이 낮아질수록 보석을 받는 학생 수가 늘어나므로, 질투심을 기준으로 Parametric Search를 돌려봅시다.

 

질투심이 \( X \) 이하가 되도록 \( A \)개의 보석을 나누면, 최소 \( \lceil A / X \rceil \)명의 학생에게 보석을 나눠줘야 합니다.

그러니 이를 모든 종류의 보석에 돌려줬을 때의 결과 \( \sum_{i=1}^{N} \lceil A_{i}/X \rceil \)를 계산한 뒤, 이게 \( N \) 이하라면 질투심을 더 낮춰보고, 아니면 질투심을 더 높여주면 됩니다.

 

시간복잡도는 \( O(N \log 2 \cdot 10^9) \)가 됩니다.

ll arr[300020];

void Main(){
	ll n, m; cin >> m >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll st = 1, ed = 2e9, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += (arr[i]+mid-1)/mid; }
		if (res <= m){ ed = mid-1; ans = mid; } else{ st = mid+1; }
	}
	cout << ans;
}

7. [2512] 예산 (Silver III)

상한을 \( X \)라고 합시다. 자명하게, 상한을 낮게 잡을 수록 배정 금액이 낮아집니다.

그러니 파라메트릭 서치로 잘 풀어주면 될 것 같습니다.

 

상한이 \( X \)일 때 배정되는 예산은 다음과 같이 구할 수 있습니다. \( \sum_{i=1}^{N} \min (A_{i}, X) \)

이 예산이 총 예산을 넘는다면 상한을 작게, 아니라면 상한을 크게 잡아주면 됩니다.

ll arr[10020];

void Main(){
	int n; cin >> n; ll mx = 0;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; mx = max(mx, arr[i]); }
	ll m; cin >> m;
	ll st = 1, ed = mx, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += min(arr[i], mid); }
		if (res <= m){ st = mid+1; ans = mid; } else{ ed = mid-1; }
	}
	cout << ans;
}

8. [1072] 게임 (Silver III)

승률이 한 번 바뀐 뒤로는 더 오르거나 / 가만히 있기 때문에 안 바뀐 상태로 돌아가는 경우는 없습니다.

그러니 파라메트릭 서치를 사용해서 추가 플레이 횟수를 구해봅시다.

 

\( P \)회 게임을 더 한 뒤의 승률은 \( \left\lfloor 100 \cdot \frac{X+P}{Y+P} \right\rfloor \text{%} \)가 됩니다. 그러니 이 값이 원래 있던 Z와 다른지 판별해주면 됩니다.

\( [1, 10^12] \) 구간에서 돌려주면 답이 잘 나옵니다.

아무리 돌려도 Z가 변하지 않는다면 -1을 출력해야 함에 주의하세요.

void Main(){
	ll x, y; cin >> x >> y;
	ll z = 100*y / x;
	ll st = 1, ed = 1e12, ans = -1;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 100 * (y+mid)/(x+mid);
		if (z != res){ ed = mid-1; ans = mid; } else{ st = mid+1; }
	}
	cout << ans;
}

9. [2805] 나무 자르기 (Silver III)

높이가 낮아질수록 가져갈 수 있는 나무의 길이는 길어집니다.

그러니 최적의 높이를 Parametric Search로 찾아봅시다.

 

높이를 \( X \)미터로 설정했을 때 가져갈 수 있는 나무의 길이는 \( \sum_{i=1}^{n} \max(A_{i}, 0) \)입니다.

그러니, 저 길이가 목표인 \( M \)보다 크거나 같다면 더 높은 높이를, 아니면 더 낮은 높이를 시도해보면 됩니다.

 

시간복잡도는 \( O(N \log 10^9) \)입니다.

ll arr[1000020];

void Main(){
	int n; ll m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll st = 0, ed = 1e9, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += max(arr[i]-mid, 0LL); }
		if (res >= m){ st = mid+1; ans = mid; } else{ ed = mid-1; }
	}
	cout << ans;
}

10. [2613] 숫자구슬 (Gold II)

그룹의 합의 최댓값이 클 수록 그룹의 개수는 작아질테니, 그룹의 합의 상한선을 기준으로 Parametric Search를 돌려봅시다.

 

만약 그룹의 합이 \( X \)를 넘지 못한다면, 어떻게 합쳐야 할까요?

다양한 방법이 있겠지만, 1번 그룹만을 보면 '되는대로 합친다'가 답이 됩니다.

그럼 이를 토대로 2번 그룹을 보면 역시 '되는대로 합치는' 게 최적이고,

이런 식으로 모든 그룹에 대해 "합이 넘지 않는 동안 계속 합친다"를 해주는 게 최적입니다.

 

이런 식으로 그룹을 합쳤을 때 \( M \)개 이하의 그룹이 만들어졌다면 더 작은 최댓값을 탐색하고, 아니면 더 큰 최댓값을 탐색해보면 됩니다.

 

주의할 점으로는, 그룹의 개수가 정확히 \( M \)개여야 하지만, 위 방식으로는 정확히 \( M \)개가 아닌 경우가 만들어질 수도 있습니다.

이 경우, 그냥 \( M \)개가 될 때까지 마음대로 더 잘라주면 됩니다.

 

+ 마음대로 더 자르다가 최댓값이 더 작아지면 어떡해야 하죠?

만약 최댓값이 더 작아질 수 있다면 그걸 Parametric Search에서 잡아냈을 테니, 그런 경우는 없습니다.

int arr[320];

void Main(){
	int n, m; cin >> n >> m; int mx = 0;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; mx = max(mx, arr[i]); }
	int st = mx, ed = 30000, ans = 0;
	while (st <= ed){
		int mid = st+ed >> 1;
		int sum = 0, res = 1;
		for (int i = 1; i <= n; i++){
			sum += arr[i];
			if (sum > mid){ sum = arr[i]; res += 1; }
		}
		if (res <= m){ ed = mid-1; ans = mid; } else{ st = mid+1; }
	}
	vector<int> anv;
	int sum = 0, ptr = 1;
	for (int i = 1; i <= n; i++){
		sum += arr[i];
		if (sum > ans){ anv.push_back(i-ptr); sum = arr[i]; ptr = i; }
	}
	anv.push_back(n+1-ptr);
	cout << ans << endl;
	int vl = anv.size();
	for (int& x : anv){
		while (vl < m){
			if (x == 1){ break; }
			cout << 1 << ' ';
			x -= 1; vl += 1;
		}
		cout << x << ' ';
	}
}

11. [3745] 오름세 (Gold III)

오름세의 정의를 생각해보면, Increasing Sequence와 동일함을 알 수 있습니다.

그 중 가장 긴 (Longest) 걸 찾아야 하니, 정직한 LIS 문제임을 알 수 있습니다.

int arr[100020], lis[100020];

void Main(){
	int n; while (cin >> n){
		for (int i = 1; i <= n; i++){ cin >> arr[i]; }
		int cnt = 0;
		for (int i = 1; i <= n; i++){
			auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
			if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
		}
		cout << cnt << endl;
		for (int i = 0; i < cnt; i++){ lis[i] = 0; }
	}
}

12. [2352] 반도체 설계 (Gold III)

꼬이지 않도록 연결한다는 건, \( i < j \)일 때 \( A_{i} < A_{j} \)라는 것입니다.

그러니, 이 개수가 최대라는 건 \( i_{1} < i_{2} < \cdots < i_{k} \)일 때 \( A_{i_{1}} < A_{i_{2}} < \cdots < A_{i_{k}} \)인 \( k \)를 최대화해야 한다는 것입니다.

 

뭔가 익숙하지 않나요? 방금 설명한 문제는 LIS 문제와 동일합니다.

그러니, 꼬이지 않는 연결선의 개수 = LIS의 길이가 됩니다.

 

\( N \le 40000 \)이니 \( O(N \log N) \)으로 구해줘야 합니다.

int arr[40020], lis[40020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
		if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
	}
	cout << cnt;
}

13. [1365] 꼬인 전깃줄 (Gold III)

자르는 전선의 개수를 최소화하는 것과 꼬이지 않는 전깃줄의 개수를 최대화하는 건 동일하므로, 꼬이지 않는 전깃줄의 개수를 세봅시다.

 

그런데 꼬이지 않는 전깃줄의 개수는 12. [2352] 반도체 설계 문제에서 이미 구해봤습니다.

즉, LIS의 길이가 됩니다.

 

이번에는 자르는 전선의 개수이니, N - (LIS의 길이)를 출력해주면 됩니다.

\( N \le 100000 \)이니, \( O(N \log N) \)으로 풀어주면 됩니다.

int arr[100020], lis[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
		if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
	}
	cout << n-cnt;
}

14. [10025] 게으른 백곰 (Silver IV)

\( [x-K, x+K] \) 구간에서 \( [x+1-K, x+1+K] \) 구간으로 이동할 때는 \( A_{x+1+K} \)를 더한 뒤 \( A_{x-K} \)를 빼주면 됩니다.

그러니 우선 \( [-2K, 0] \) 구간에서의 얼음 개수를 구한 뒤, 이를 오른쪽으로 1칸씩 밀어주면서 최댓값을 구해주면 됩니다.

 

시간복잡도는 \( O(X=10^6) \)입니다.

ll arr[1000020];

void Main(){
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		arr[y] += x;
	}
	ll ans = 0, res = 0;
	for (int i = 0; i <= 1000000; i++){
		int j = i - 2*k - 1;
		if (j >= 0) res -= arr[j];
		res += arr[i];
		ans = max(ans, res);
	}
	cout << ans;
}

15. [2467] 용액 (Gold V)

입력으로 들어오는 \( A \)는 오름차순으로 정렬되어있습니다.

그러니 바로 두 포인터를 p1 = 1에, p2 = N에 놓고 시작해봅시다.

 

만약 \( A_{p1} \)과 \( A_{p2} \)의 부호가 같다면, \( |A_{p1} + A_{p1+1}| \)과 \( |A_{p2-1} + A_{p2}| \) 중 더 작은 걸 찾고 끝내면 됩니다.

그렇지 않다면, \( A_{p1} \le 0 \le A_{p2} \)입니다.

만약 \( |A_{p1}| < |A_{p2}| \)라면 p2를 움직여주면 되고 (p2 -= 1),

그렇지 않다면 p1을 움직여주면 됩니다 (p1 += 1).

 

답은 두 포인터를 이동하면서 만난 모든 \( |A_{p1} + A_{p2}| \) 중 최솟값이고, 이 때의 \( A_{p1}, A_{p2} \)를 출력해주면 됩니다.

 

시간복잡도는 \( O(N) \)입니다.

ll arr[100020];

ll ans = 1e15, x=0, y=0;
void f(int p1, int p2){
	ll res = abs(arr[p1] + arr[p2]);
	if (ans > res){ ans = res; x = arr[p1]; y = arr[p2]; }
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int p1 = 1, p2 = n;
	while (p1 < p2){
		f(p1, p2);
		if (arr[p1] > 0){ f(p1, p1+1); break; }
		if (arr[p2] < 0){ f(p2-1, p2); break; }
		if (abs(arr[p1]) <= abs(arr[p2])){ p2 -= 1; }
		else{ p1 += 1; }
	}
	cout << x << ' ' << y << endl;
}

사실 이 문제는 이진 탐색만으로도 풀 수 있습니다.

 

1번 용액 \( x \)를 고정한다면, 2번 용액은 \( -x \)에 가장 가까운 값으로 선택해야 하므로,

\( -x \)를 기준으로 이진 탐색을 해줘서 \( -x \) 미만의 수 중 가장 큰 수와 \( -x \) 이상의 수 중 가장 작은 수 2개를 찾을 수 있고, 둘 중 더 좋은 해를 선택해주면 됩니다.

 

시간복잡도는 \( O(N \log N) \)입니다.

ll arr[100020];

ll ans = 1e15, x=0, y=0;
void f(int p1, int p2){
	ll res = abs(arr[p1] + arr[p2]);
	if (ans > res){ ans = res; x = arr[p1]; y = arr[p2]; }
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		int j1 = lower_bound(arr+1, arr+n+1, -arr[i]) - arr;
		int j2 = j1 - 1;
		if (j1 == i){ j1 += 1; } if (j2 == i){ j2 -= 1; }
		if (j1 <= n){ f(i, j1); }
		if (1 <= j2){ f(i, j2); }
	}
	if (x > y){ swap(x, y); }
	cout << x << ' ' << y;
}