백준 9007 카누 선수 c++ (이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/9007

9007번: 카누 선수

 

 

풀이

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int t;
//1<=k<=40000000
//1<=n<=1000
//1<=몸무게<=10000000

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	
	cin >> t;
	while (t--) {
		int k, n;
		cin >> k >> n;
		int temp[1000];
		vector<int> vt1(n*n);
		vector<int> vt2(n*n);
		for (int i = 0; i < n; i++) {
			cin >> temp[i];
		}
		int idx = 0;
		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			for (int j = 0; j < n; j++) {
				vt1[idx++] = temp[j] + num;
			}
		}
		for (int i = 0; i < n; i++) {
			cin >> temp[i];
		}
		idx = 0;
		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			for (int j = 0; j < n; j++) {
				vt2[idx++] = temp[j] + num;
			}
		}
		sort(vt1.begin(), vt1.end());
		sort(vt2.begin(), vt2.end());
		int answer=987654321;
		bool flag =false;
		for (int i = 0; i < vt1.size(); i++) {
			int left = 0;
			int right = vt2.size();
			while (left < right) {
				int mid = (left + right) / 2;
				int result = vt2[mid] + vt1[i];
				if (result == k) {
					answer = result;
					flag = true;
					break;
				}
				if (abs(k-result) == abs(k - answer)) {
					answer = min(answer, result);
				}
				else if (abs(result - k) < abs(answer - k)) {
					answer = result;
				}
				if (result < k) {
					left = mid+1;
				}
				else {
					right = mid;
				}
			}
			if (flag) break;
		}
		cout << answer << '\n';
	}

	return 0;
}

ㅇㅁㄹ