[BOJ-2470]두용액

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

입력으로 용액의 특성값이 주어진다. 두용액을 더했을 때 0에 가까운 값을 가지는 두 특성값을 작은 값, 큰 값을 출력한다. 

[문제 풀이]

먼저 입력으로 주어지는 수를 정렬을 한다.

1. 그런 후 양쪽에 있는 수(새로운 합)를 더한다.
1. 더한 수가 현재 저장하고 있는 값(이전 합)보다 작다면 갱신한다.
2. 만약 새로운 합이 양수라면 양수쪽 값을 더 작게하기 위해 뒤 위치에서 하나내린다.
3. 만약 새로운 합이 음수라면 음수쪽 값을 더 작게하기 위해 앞 위치에서 하나올린다.
2. 값을 출력한다.

위 과정으로 구할 수 있다. 

[C++ source code]

#include<iostream>
 
struct minheap {
    int d[1<<18];
    int e;
    minheap() {    e = 0; }
    void clear() { e = 0; }
    bool empty() { return e == 0; }
    bool full() { return (e + 1) == (1 << 18); }
    void push(int i) {
        if (full()) return;
        d[++e] = i;
        int cur = e;
        while (cur / 2 > 0) {
            if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]);
            else break;
            cur /= 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        int cur = 1;
        while (2 * cur <= e) {
            int child;
            if (2 * cur + 1 > e) {
                child = 2 * cur;
            }
            else {
                child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1;
            }
 
            if (d[cur] < d[child]) break;
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    void swap(int& a, int& b) { int t = a; a = b; b = t; }
    int top() {
        if (empty()) return -1;
        return d[1];
    }
};
 
int mabs(int a) {
    return (a > 0) ? a : -a;
}
 
int im[1 << 18];
minheap PQ;
int main() {
    int N;
    scanf("%d", &N);
    for (register int i = 0; i < N; ++i) {
        scanf("%d", &im[i]);
        PQ.push(im[i]);
    }
    for (register int i = 0; i < N; ++i) {
        im[i] = PQ.top();
        PQ.pop();
    }
 
    int s = 0;
    int e = N - 1;
    int c_diff = 2000000001;
    int ans[2];
    while (s < e) {
        int diff = im[s] + im[e];
        if (diff == 0) {
            ans[0] = im[s];
            ans[1] = im[e];
            break;
        }
        else if (diff > 0) {
            if (mabs(c_diff) > mabs(diff)) {
                c_diff = diff;
                ans[0] = im[s];
                ans[1] = im[e];
            }
            e--;
        }
        else if (diff < 0) {
            if (mabs(c_diff) > mabs(diff)) {
                c_diff = diff;
                ans[0] = im[s];
                ans[1] = im[e];
            }
            s++;
        }
    }
 
    printf("%d %d\n", ans[0], ans[1]);
 
    return 0;
}