17124 두 개의 배열

이진 탐색 문제

실패로 끝남

1. 문제

---

간단 설명

n개의 양수를 가지는 A 배열

m개의 양수를 가지는 B 배열이 있다

C 배열을 만드는데,

A_0부터 시작해서 A_(n-1) 까지 순서대로 시작한다

B 배열의 원소 중에서 A_0 원소와의 차이의 절대값이 가장 작은 값을 C에 넣는다

abs(b[j] - a[i]) 가 가장 작은 값을 C에 넣는것

C의 원소들의 합을 구하는 문제

2. 문제 분석

---

필요변수

테스트케이스의 수 T

A와 B의 원소의 개수 n, m

a, b 배열 vector<int> a, b

a, b의 원소의 개수는 최대 10^6개

배열 C는 원소들의 합만 구하면 되므로 int sum으로 처리함

주의점

• nested loop으로는 시간초과가 발생함
  • 10^6 * 10^6 이므로 1조정도

알고리즘

시도한 첫번째 방법

Binary Search를 이용해 B의 원소에 접근했다

그러나 예제는 통과했으나 반례를 찾지 못해서 실패

1. 입력받기
2. 각 원소 a_i 에 대해서 배열 b에서 binary Search 돌림
3. 이분 탐색이 종료된 지점을 기준으로 양옆의 원소를 확인함
4. 총 3개의 원소, 종료된 지점의 왼쪽, 종료된 지점, 오른쪽 값을 절대값을 계산한 뒤
5. 최소값을 sum에 추가하고 다음 원소로 이동

뭐가 문제인지 아직 해결 못했음

3. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int n, m;
vector<int> a, b;
int sum;

void Input() {
	cin >> n >> m;
	a.clear();  a.resize(n);
	b.clear();  b.resize(m);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	sort(b.begin(), b.end());
}

// binary search를 돌리면 값을 찾거나,
// 근처까지 가서 인덱스를 반환함
int My_Binary_Search(int start, int end, int target) {
	int mid;

	while (start < end) {
		mid = (start + end) / 2;
		if (b[mid] == target) return mid;
		if (target < b[mid]) {
			end = mid -1;
		}
		else {
			start = mid + 1;
		}
	}

	return mid;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	int T;
	cin >> T;
	while (T--) {
		Input();

		sum = 0;

		for (int i = 0; i < n; i++) {
			int prox_idx = My_Binary_Search(0, b.size() - 1, a[i]);
			
			// 이 주위의 값을 확인한다 [ prox_idx-1 ~ prox_idx+1 ]
			vector<int> v;
			v.push_back(b[max(prox_idx - 1, 0)]); // prox_idx 가 0 이하로 내려가는걸 방지
			v.push_back(b[prox_idx]);
			v.push_back(b[min(prox_idx + 1, m-1)]); // prox_idx 가 m 이상 넘어가는걸 방지

			int min_diff = 21e8, min_val;
			for (int e : v) {
				int diff = abs(e - a[i]);

				if (diff < min_diff) {
					min_diff = diff;
					min_val = e;
				}
			}

			//cout << "=====DEBUG V LOG=====" << endl;
			//cout << "a[i] : " << a[i] << endl;
			//for (int e : v) {
			//	cout << e << endl;
			//}
			//cout << "min_val : " << min_val << endl;
			//cout << "=====================" << endl;

			sum += min_val;
			
		}
		
		 cout << sum << endl;
	}

	return 0;
}