[BOJ]2467-溶液

これは,並べ替え後の配列に2つの値を加え,0に最も近い2つの値を探す問題である.
解題ポリシー
答えを出す.
初めてこの問題をするときは二重ポインタを使いました.
始点と終点を指定した後、2つの値が0より大きい場合は終点を減らし、0より小さい場合は始点を増やします.
この方法で,O(n)は十分に解ける.
説明する.
もう一つの解釈は二分探索を用いることができる.
0に最も近い値を探す問題なので、現在の値の負の値に最も近い値を見つければいいのです.
たとえば、現在のブラウズ値が8の場合、0に最も近い値は-8に最も近い値でなければなりません.
したがって、現在検索されている値を負に変換する値は、指定された配列に見つかればよい.
このプロシージャを配列の最初の値から最後の値に繰り返すとよい.
コード#コード#

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int n;
vector<int> v;
int target = 2000000000;
void f1_tp(){
    int s = 0;
    int e = v.size()-1;
    int ans[2] = {-1,-1};

    while(s < e){
        int sum = v[s] + v[e];
        if(abs(sum) < target){
            ans[0] = v[s];
            ans[1] = v[e];
            target = abs(sum);
        }
        if(sum >= 0){
            e--;
        }else{
            s++;
        }
    }
    cout << ans[0] << " " << ans[1] << "\n";
}

void f2_bs(){
    int ans[2] = {-1,-1};
    for(int i=0;i<v.size();i++){
        int idx = lower_bound(v.begin(), v.end(), -v[i]) - v.begin();
        for(int j = idx-1;j<=idx;j++){ // idx-1 vs idx
            if(j == i || j<0 || j>=n)
                continue;
            if(v[j] + v[i] == 0){
                ans[0] = v[j];
                ans[1] = v[i];
                if(ans[0] > ans[1])
                    swap(ans[0], ans[1]);
                cout << ans[0] << " " << ans[1] << "\n";
                return;
            }else{
                if(target <= abs(v[j] + v[i]))
                    continue;
                ans[0] = v[j];
                ans[1] = v[i];
                target = abs(v[j] + v[i]);
            }
        }
    }
    if(ans[0] > ans[1])
        swap(ans[0], ans[1]);
    cout << ans[0] << " " << ans[1] << "\n";
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    //f1_tp(); // two pointer
    f2_bs(); // binary search
}

ソース
https://www.acmicpc.net/problem/2467