[Alogithm]入国審査

プログラマー-入国審査問題の解決

:等級検査lv 3この問題で合格しなかった...残りの問題ははっきり覚えていませんが、この問題はDBで解決されています(フィボナッチタイプ).残念ながらlv 3は再挑戦!今日はこの問題を探しに来ました.
質問リンク

もんだいぶんせき

:質問では、指定された審査官の情報に基づいて、待機している人数を審査する場合、すべての人を審査するのに必要な最小値は数時間です.

問題の分析と解決策

:最初はクイッククリアの審査官に待機者(?)を手配します.彼を最後まで待たせる人は審査員が少ない時より効率が高い(?)方法で最小値を作るかもしれないと思います.なぜなら、Rainは、まず、審査官なしで作るのが最も効率的だと考えているからだ.しかし、1つの審査官が1万個解決し、1つの審査官が10万個解決すれば、1万個解決可能な審査官を何回回して(?)能率が高い.つまり、1万能解決の審査が終わってからその人に送ったほうがいいということで、席が空いていたので10万で終わった審査官に送ったとしたら、効率的ではありません.これで、問題はどう解決しますか??これが私の最後の理由です.言(?)いいえ、これは私がこの問題を解決できなかったのは最後です.
この問題のポイントは「審査を終える最短時間」を求めることです.そのため、完全探索を行う制限が大きすぎる(10億).このように,特定の数(審査が完了できる最短時間)を求めるためには,より効率的なアルゴリズムを見つける必要がある.この時、じゃんけんの方法ではここでは通用しません.実はここで「この探求」の人の頭がどうなっているのか知りたいです...この探索を考えてこそ答えられる問題だ.少し逆思考が必要な部分は、待っている人をどの審査官に投入するかではなく、「数時間の時間を与えて審査を終わらせる」ことを考えています.私に最大の時間をください.もしその時間内に審査できるなら?時間を減らす.もしよろしければ?もう少し小さくしてこのように縮小すると、不可能なポイントがいくつかあり、その限界の可能時間は最小時間です.実際,これも完全探索のように時間がかかるため,この探索を二分探索として効率(logn)を向上させる.
再整理する場合は、最短の時間を探すために、1から最悪の場合(最長の時間)までの時間をよく考えて(完全探索).では、いつか所定の人数で審査できないポイントがあります.では、それまでに見られる審査のポイントが正解です.しかし,この方法は時間的複雑さでソートする必要があるため,ここである値を検索する際に最も有効なアルゴリズム二分探索を用いる.
**この探索を思い出したいなら、もっと問題を作るしかない.
いずれにしても、最低限の審査時間を求めることがポイントなので、私のような場合、「実施」問題を解決する際のように、実際の審査過程をシミュレートしようとしたが、そうではなく、最悪の時間から順次審査時間を与え、最小値を探す考えを思いつき、そこでこの探索を思いついた.実はもっと重要なのは、最悪の時間から順番に与えて、最小値を探す考えです.

マイコード

def solution(n, times): maximum_time = max(times) * n minimum_time = 1 answer = 0 while minimum_time <= maximum_time: mid_time = (maximum_time + minimum_time) // 2 people_cnt = 0 for time in times: people_cnt += mid_time // time if people_cnt >= n : maximum_time = mid_time - 1 answer = mid_time elif people_cnt < n: minimum_time = mid_time + 1 return answer

の最後の部分

:これからは必ずもう一度解いてください.審査官の能力(審査に要する時間)に応じて、最悪の時間から順番に審査を適用して待機できる人数を確定し、適任であれば与える時間を減らすことができる.耐えられなければ、与えられた時間を延長して、その限界(耐えられない、耐えられない)を探す考え...!