https://www.acmicpc.net/problem/17124
17124번: 두 개의 배열
정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있
www.acmicpc.net
C[i]는 배열 B에 있는 값 중에 A[i]에 가장 가까운 값이고 가장 가까운 값이 2개면 더 작은값입니다.
배열의 크기가 100만이므로 선형으로 찾기에는 무조건 시간초과이므로 이분탐색을 사용합니다.
(이분탐색을 위해 B 배열을 정렬해줍니다.)
A[i]가 주어지면
B 배열에서 A[i]보다 작은 값중에 가장 큰 값 = l
B 배열에서 A[i]보다 큰 값중에 가장 작은 값 = r
이러면 l과 r 둘중에 하나는 정답입니다.
abs(A[i] - l) vs abs(A[i] - r)를 비교하여 차이가 적은 값 (차이가 같으면 둘 중에 작은 값) 을 ans에 더해줍니다.
배열에 10^9까지 올 수 있으므로 long long 타입으로 계산하였습니다.
|
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;
typedef long long ll;
int A[1000001], B[1000001];
int N, M;
ll ans;
int largesearch(int l, int r, int x) {
int m = (l + r) / 2;
if (B[m] == x) return B[m];
else if (B[m] > x) {
if (l == m) return B[m];
else return min(B[m], largesearch(l, m - 1, x));
}
else {
if (m == r) return INF;
else return largesearch(m + 1, r, x);
}
}
int smallsearch(int l, int r, int x) {
int m = (l + r) / 2;
if (B[m] == x) return B[m];
else if (B[m] < x) {
if (m == r) return B[m];
else return max(B[m], smallsearch(m + 1, r, x));
}
else {
if (l == m) return -1;
else return smallsearch(l, m - 1, x);
}
}
void func() {
int l = 0, r = 0;
for (int i = 1; i <= N; i++) {
l = smallsearch(1, M, A[i]);
r = largesearch(1, M, A[i]);
if (l == -1) l = B[1];
if (r == -1) r = B[M];
if (abs(A[i] - l) <= abs(r - A[i])) {
ans += l;
}
else ans += r;
}
cout << ans << '\n';
}
void input() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
for (int i = 1; i <= M; i++) {
cin >> B[i];
}
sort(B + 1, B + 1 + M);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
ans = 0;
}
return 0;
}
|
cs |
'algorithm > binarysearch' 카테고리의 다른 글
| boj 2110 공유기 설치 (0) | 2021.04.13 |
|---|---|
| boj 7453 합이 0인 네 정수 (0) | 2021.01.22 |
| boj 2143 두 배열의 합 (0) | 2021.01.22 |
| boj 2805 나무 자르기 (0) | 2021.01.22 |
| boj 1920 수 찾기 (0) | 2021.01.22 |