카누 선수


작성일 : 2017-01-18 02:03:22
조회수 : 573



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


$n=1000$ 이기 때문에, 4중 for문을 통한 $O(n^4)$ 의 방법으로는 제한시간인 3초만에 풀 수 없습니다. 그러므로 시간 복잡도를 줄이기 위해서 1번째 리스트와 2번째 리스트, 그리고 3번째 리스트와 4번째 리스트의 모든 합을 구한 다음, 한 쪽을 정렬하여 Binary search를 통해 찾아주면 됩니다. 이 때의 시간 복잡도는 $O(n^2log(n^2))$ 이 됩니다.

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll w[4][1001], p[1000001], q[1000001];
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        ll k, n, t = 0, A;

        cin >> k >> n;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < n; j++) cin >> w[i][j];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                p[t] = w[0][i] + w[1][j], q[t++] = w[2][i] + w[3][j];

        sort(q, q + t);
        A = p[0] + q[0];
        for (int i = 0; i < t; i++)
        {
            int s = 0, e = t - 1, M;
            while (s <= e)
            {
                M = (s + e) / 2;
                ll u = p[i] + q[M];
                ll l = abs(k - A), r = abs(k - u);
                if (l >= r) A = l == r ? min(A, u) : u;
                if (u < k) s = M + 1;
                else e = M - 1;
            }
        }
        cout << A << "\n";
    }
}

카누 선수 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글