[アルゴリズム解析解析解析]Programmers入国審査

今日解答した問題はプログラマーが探索中の入国審査です!
このナビゲーションアルゴリズムはほとんど解読されていないようで、やはり近づきにくくて、間違った方法で接近して、最後に検索を通じて助けて解決しました、、、、!
完璧な一人で解決するのではなく、残念で、悲しいです.
アルゴリズムを解読したいのですが、容易ではありません.

プログラマー入国審査

質問リンク
所要時間はそれぞれ異なる入国審査隊があり、n人の人員を審査するのに最も時間がかかる問題である.

I/Oと制限

私の答え

この探索カテゴリの問題なので「この探索を使う->バイナリツリーを使う->「n人をバイナリツリーにする?」これでとても単純で無知な思考回路を回しました...!
今考えてみれば、n人でバイナリツリーを作るのは本当にでたらめだ.
n個人の情報以外に、何の条件もなく、何の特徴もなく、いったい何で李真樹と羅抜高校を構成したのか...!
そしてこの探索->李真樹?年配の方も残念
この探索:最初から最後まですべてを確認せず、いかなる基準で半分に分けて探索する過程!
久しぶりに会ったせいか、おでこも忘れたのか、うわっ
問題に関する布告を探索するのは,n人ではなく,n人を審査するのに要する時間を二分的に探索することであり,また問題を解いてみる.

ソリューション

この探求が必要な範囲を探るために!
n名を審査するのにかかる時間の最高価格と最低価格は何ですか?
最高値はもちろん1です.
最低価格は最長時間の審査台でn人全員が審査を受ける場合かもしれない.
もしそうであれば、問題の例については、次のようになります.
最初の二分探索は[1,60]から始まる.
この区間の中間値を30分としたらどうなりますか?
7分かかる審査団A 10分の審査団Bの場合
30分以内にA組が4人(30/7)、B組が3人(30/10)で審査を受け、合計7人で審査が可能
私たちは6人を審査するだけなので、小さな範囲[1,29]からこの人を探求し始めました.
このようにして30分以内に6人を審査する時間
この時、私が一番困ったのは、この問題の核心部分は、6人を審査できる時間の中で、最高価格を見つけることです.
私はこの部分の実現に少し工夫を凝らして、いくつかの位置づけを参考にして完成しました.
まず、検索範囲[min,max]の範囲内で、minがmaxを超えるまで繰り返し文を検索し、n名でレビューを行うmidが見つかった場合は、そのmidを仮解答として保存し、より小さなmid値が見つかった場合は、更新するようにコードを記述する

コード#コード#

#include <iostream>
#include <vector>
#include <algorithm>

// 프로그래머스 이진 탐색, 입국 심사, level 3
using namespace std;

long long solution(int n, vector<int> times) {

    sort(times.begin(), times.end());

    unsigned long long left = 1;
    unsigned long long right = n*(times[times.size()-1]);
    unsigned long long mid;
    unsigned long long answer = right;

    while (left<=right){  // 최소가 최대를 추월할 때 까지 탐색
        unsigned long long count = 0;
        mid = (left+right)/2;

        // mid 시간 동안 몇명을 검사할 수 있는지 계산 count
        for (unsigned long long i = 0; i < times.size(); ++i) {
            count += mid/times[i];
        }

        if (count >= n){
            if (mid <= answer){
                // 해당 시점의 mid 값을 임시 정답으로 저장, 최소의 mid를 탐색
                answer = mid;
            }
            right = mid-1;
        }else {
            left = mid+1;
        }
    }

    return answer;
}

合格しましたが、いろいろな面で不快な問題で、
こちらの探索部分はあまり出てこないのですが、訪問経験は確かに足りないので、準備をしておきます…!
参考資料