[Algorithm]宜珍を探る?パラメトリック検索?🤔

バイナリ検索とパラメトリック検索の違いを理解する😊
最初はバイナリ検索とパラメータ検索が違う種類のアルゴリズムだと思っていましたが、ほほほ
しかし、パラメトリック検索はバイナリ検索の一種であり、バイナリ検索のタイプを利用してパラメトリック検索のタイプの問題を解決することができます!
もう一度よく尋ねる😎

バイナリナビゲーションとは、

バイナリサーチは、一連のソート値が与えられたときに、これらの値から必要な値を探すアルゴリズムです.
中間値を選択して、探している値と中間値を比較し、大きい場合は中間値が最も高く、小さい場合は中間値が最も高く、欲しい値が見つかるまでこの過程を繰り返して問題を解決します.
1つのプロセスを経るたびに,探索の範囲は半分に減少し,時間複雑度はO(log N)であり,高速な探索アルゴリズムである.
しかし欠点は、ソートされた値でなければナビゲーションができないことです!
例えばで、上から1から9の数字が与えられたと仮定すると、3を探す必要がある問題があります.
1.中間値5が3より大きいか3より小さいかを確認します.
2.3 < 5であるため、5〜9を除いて、中間値((1+4)/2 = 2.5 -> 2)と3を1〜4の間で再比較する.
3.2 < 3であり、1〜2を除いて、中間値((3+4)/2 = 3.5 -> 3)および3を3〜4の間で比較する.
4.一致するため、ナビゲーションを終了します.

パラメトリック検索バー、

パラメトリック検索はバイナリ検索とは異なり、一連の与えられた値ではなく、与えられた範囲内で必要な値または必要な条件と最も一致する値を見つけるアルゴリズムです.
バイナリ・ナビゲーションが1から9の値から3を検索する場合、
パラメトリック測定は1〜9の範囲で3を見つけた.
与えられた範囲であるため,特定の状況を最適化する問題を解決する際に用いるのがよい.
また,パラメータ化プログラムを用いて最適化問題を決定問題解に変換することができ,問題の解をかなり容易にすることができる.
簡単に言えば、場合によっては、ある特定の値(例えば最大/最小値)を求める問題(=最適化問題)は、ある特定の値がある条件を満たすことを確認するだけでよい問題(=決定問題)となる.
パラメータ化研究を用いた代表的な問題は白駿1654:網を切る題!

与えられた網線の長さによって、2^31-1以下の自然数は約20億を超え、順番に検索すると時間を超える.
私たちがまとめたパラメータ化検索方法を適用したらどうですか?😎?
答えは簡単です.
適切な長さが見つかるまで、網線の長さを繰り返し調整します.
「現在の長さは条件を満たしていますか?」この問題は「はい」「いいえ」で確認します.
これは,中間値を調節し,探索範囲を縮小することによって解決した.

from sys import stdin

K, N = map(int, stdin.readline().split())
lans = [int(stdin.readline()) for _ in range(K)]

start, end = 1, max(lans)
res = 0

while start <= end:
    mid = (start + end) // 2
    cnt = 0

    for l in lans:
        cnt += l // mid

    if cnt >= N:
        start = mid + 1
        res = mid
    else:
        end = mid - 1

print(res)

¥¥¥実際は私のコード¥
最後に、パラメトリック測定を使用する条件を理解します!
1.特定の条件を満たす最値/最切り上げ形式の問題でなければならない.
あるいは、このような形で変形できるはずです.
2.最値を求める問題に対して、ある値が条件を満たす場合、その値より小さい値はすべて条件を満たすべきである.(最大値の場合、その値より大きい値は条件を満たす必要があります.)
このようにしてこそ,条件を満たす場合に,より大きな値を決定することができ,満たさない場合には,二分探索により答えを探すことができる.
3.答えの範囲は、離散的または(e.g.整数)許容誤差の範囲でなければならない.
これは,連続した範囲で無限に正解に近づくことができるが,完全に正しい値を得ることができないためである.
参考資料1
参考資料2