9007번: 카누 선수

https://www.acmicpc.net/problem/9007


$O(tn^2\lg n)$

두 반씩 합 쌍을 모두 구해놓고 정렬한 다음, 이분 검색을 통해 두 수열에서 k에 가까운 두 수의 합을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, a[4][1000], b[1000000], n, k;
int main() {
        for (scanf("%d", &t); t--;) {
                scanf("%d%d", &k, &n);
                int r = 1e9;
                for (int i = 0; i < 4; i++)
                    for (int j = 0; j < n; j++) scanf("%d", a[i] + j);
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++) b[i*n + j] = a[2][i] + a[3][j];
                sort(b, b + n*n);
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                                int s = a[0][i] + a[1][j], p = lower_bound(b, b + n*n, k - s) - b;
                                if (p<n*n && (abs(r - k)>abs(s + b[p] - k) || abs(r - k) == abs(s + b[p] - k) && r>s + b[p])) r = s + b[p];
                                if (p && (abs(r - k)>abs(s + b[p - 1] - k) || abs(r - k) == abs(s + b[p - 1] - k) && r>s + b[p - 1])) r = s + b[p - 1];
                        }
                }
                printf("%d\n", r);
        }
        return 0;
}