[アルゴリズム解解析]BOJ 2467溶液

さんざん殴られた面接週間が終わり、NaverCoteは土曜日!Algol時給!!
今日の問題はBOJ 2467溶液です.この方の探索問題だと聞いて入ってみましたが、まず二つの針を二つの針で解いてから再び二分探索で解いたと思います

BOJ 2467溶液

KOI建設科学研究所は多様な酸性溶液とアルカリ性溶液を持っている.各溶液には整数があり、その溶液の特性を表す.酸性溶液の特性値は、1〜10000000の正の整数で表され、塩基性溶液の特性値は−1〜10000000の負の整数で表される.
2つの溶液を等量混合した溶液の特性値は、混合に用いられる各溶液の特性値の和として定義される.この研究所は等量の2種類の溶液を混合し,特性値が最もゼロに近い溶液を作製しようとしている.
例えば、与えられた溶液の特性値が[−99、−2、−1,4,98]であり、特性値が−99の溶液と特性値が98の溶液とが混合されると、特性値が−1の溶液が得られ、この溶液の特性値が0に最も近い溶液が得られる.ちなみに、特性値が0に近い混合溶液を2種類のアルカリ溶液または2種類の酸性溶液のみで製造する場合もある.
酸性溶液とアルカリ性溶液の特性値がソート順に並んでいる場合は、プログラムを作成し、その中の2つの異なる溶液を混合し、特性値が0に近い2つの溶液を見つけます.

にゅうしゅつりょく

[入力]
1行目は、溶液全体の数Nを入力する.Nは2以上100000以下の整数である.2行目では、溶液特性値を表すN個の整数が、スペースを介して昇順に入力され、これらの数字はいずれも−10000000または10000000以下である.N個の溶液の特性値が異なり、酸性溶液またはアルカリ性溶液のみが入力される場合もある.
[出力]
1行目の出力特性値は0に近い2つの溶液の特性値である.出力が必要な2種類の溶液は特性値の昇順に出力される.プロパティ値が0の場合、2つ以上の場合、いずれかを出力します.

私の答え

ダブルポインタ

問題を見るとすぐに思いつく方法はダブルポインタです.
図点は整列した場合に使用する必要がありますが、入力条件には昇順に並べて入力するため、個別のソートを行う必要はありません.
溶液アレイでは、2つの変数は、それぞれleft、rightポインタから始まる.
2つのポインタが指す2つの数の合計left = 00が0に近い場合、正解が更新され、right = numbers.size()-10が0より小さい場合、sum0が0より大きい場合が実行される.
2つのポインタsumとleft++が反転する前にナビゲーションを行い,全O(N)時間で正解を得ることができる.

バイナリタワー

二分探索を練習したいという問題ですが、なぜ二分探索を利用したのか思い出せません.
いくつかの参考資料が見出され、方法は、基準溶液を昇順に捉え、その後、この溶液に最も近い他の溶液を探索することによって発見される.
合計N個の溶液right--を基準として、leftの範囲内で2つの変数right,i = 0 ~ N-2の中間位置i+1 ~ N-1と指定された溶液とのフィッティングを計算した.
その後、合計が0に近い場合は更新され、合計が0未満の場合はleftが実行され、0より大きい場合はrightが実行され、範囲が半分に縮小される.
この場合、mid、left = mid+1は同じ場合でも0に近い総和となる可能性があるので、right=mid-1にナビゲートすれば、総O(Nlogn)時間内に正解が得られる.

コード#コード#

ダブルポインタ

#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>

// boj 2467 용액, 투포인터 사용, 골드 5
using namespace std;

vector<long long> numbers;

pair<long long, long long> getBestPair(){
    pair<long long, long long> answer;
    int left = 0, right = numbers.size()-1;
    long long best_sum = LLONG_MAX;

    while (left<right){
        int sum = numbers[left] + numbers[right];

        if (abs(sum) < best_sum){
            best_sum = abs(sum);
            answer.first = numbers[left];
            answer.second = numbers[right];
        }

        if(sum < 0) left++;
        else right--;
    }

    return answer;
}

int main() {
    int N;
    cin>>N;

    numbers.assign(N, 0);
    for (int i = 0; i < N; ++i) cin>>numbers[i];

    pair<long long,long long> answer = getBestPair();
    cout<<answer.first<<" "<<answer.second;

    return 0;
}

バイナリナビゲーション

#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>

// boj 2467 용액, 이진탐색, 골드 5
using namespace std;

vector<long long> numbers;

pair<long long, long long> getBestPair(){
    pair<long long, long long> answer;
    long long best_sum = LLONG_MAX;

    for(int i=0; i<numbers.size()-1; i++){
        int flag = numbers[i];
        int left = i+1, right = numbers.size()-1;

        while (left<=right){
            int mid = (left+right)/2;
            int sum = flag + numbers[mid];

            if (best_sum > abs(sum)){
                best_sum = abs(sum);
                answer.first = numbers[i];
                answer.second = numbers[mid];
            }

            if (sum<0) left = mid+1;
            else right = mid-1;
        }
    }

    return answer;
}

int main() {
    int N;
    cin>>N;

    numbers.assign(N, 0);
    for (int i = 0; i < N; ++i) cin>>numbers[i];

    pair<long long,long long> answer = getBestPair();
    cout<<answer.first<<" "<<answer.second;

    return 0;
}