용액

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

2467번: 용액

제한 시간이 1초다. 

O(N^2)을 쓰면 무조건 시간 초과가 나겠다.

오름차순까지 주어졌으니 투 포인터를 써야하는게 뻔하다. 

 

// 두 개의 합이 0보다 작다면 0보다 가깝게 되려면 left++

        if (tmp < 0)

            left++;

// 두 개의 합이 0보다 크다면 0보다 가깝게 되려면 right--

        else

            right--;

 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    vector<long> liquid(n,0);
 
    for (int i = 0; i < n; i++)
    {
        cin >> liquid[i];
    }
 
    int left = 0;
    int right = n - 1;
 
    long sum = abs(liquid[left] + liquid[right]);
    pair<long, long> ans = make_pair(liquid[0], liquid[n-1]);
 
    while (left < right)
    {
        long tmp = liquid[left] + liquid[right];
 
        if (abs(tmp) < sum)
        {
            sum = abs(tmp);
            ans.first = liquid[left];
            ans.second = liquid[right];
        }
 
        // 두 개의 합이 0보다 작다면 0보다 가깝게 되려면 left++
        if (tmp < 0)
            left++;
        // 두 개의 합이 0보다 크다면 0보다 가깝게 되려면 right--
        else
            right--;
    }
    
    cout << ans.first << ' ' << ans.second << '\n';
 
    return 0;
}