2467번: 용액

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


$O(n)$

용액의 산성도 a[0], a[1], ..., a[n-1]이 오름차순으로 주어져 있다고 하자.
f(x)=|a[x]+a[y]|를 최소화하는 x<y인 y라 하자.
그러면 f(x)는 단조 감소 함수이다.
따라서 x를 증가시킬 때마다 y를 적절히 감소시켜 주면 주어진 문제를 O(n)에 풀 수 있다.

#include<cstdio>
#include<cstdlib>
int n, a[100000], x, y, t = 2e9, l, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    r = n - 1;
    while (l < r) {
        if (t > abs(a[l] + a[r])) t = abs(a[l] + a[r]), x = l, y = r;
        a[l] + a[r] < 0 ? l++ : r--;
    }
    printf("%d %d", a[x], a[y]);
    return 0;
}