白準2470号:2種類の溶液

7421 ワード
バイナリナビゲーション テキストリンク
質問する
  • https://www.acmicpc.net/problem/2470
  • 異なるN個の値の中から2個を選択し、最も近い組合せ
    • を検索する.
    きろくてん
  • ナビゲーションの問題へのアクセス方法
  • すべての優先事項を理解する数
  • 探索の範囲を効果的に縮小する方法
    • 方法
  • 問題確認
  • 異なるN個の値に2つの値を追加して、最適(0)の組合せ
    • を検索する.
  • 最適な組み合わせを探すナビゲーション問題
  • まずすべての場合の検索数を理解し、
    • を効率的に検索する方法を考えます.
  • ナビゲーションが必要なすべての状況を把握
  • 所与のN個の数字の中から2個の数字のnC 2組合せ
    • を選択する.
  • より効果的に範囲を縮小する方法を探しています
  • Aを選択
  • A+B=0の場合
  • の最適な組み合わせが見つかり、ナビゲーションは
    • を終了した.
  • A+B<0の場合
  • AまたはBを再培養し、
    • の最適な組み合わせがあるかどうかを探索する.
  • では、次のことが確認されました.
  • Aに基づいて、Bより小さい値
    • を決定する必要はない.
  • Bに基づいて、Aより小さい値
    • を決定する必要はない.
  • (いずれにしても組み合わせは、その総和がより小さくなるため、最適な組み合わせから遠ざかる)
    • .
  • そのため、次の追加ナビゲーションを実行します.
  • Aを基準としてBより大きい組み合わせに縮小し、
    • に移動する.
  • Bを基準としてAより大きい組み合わせに縮小し、
    • に移動する.
  • A+B>0の場合
  • AまたはBをさらに低減することにより、最適な組合せ
    • が存在するか否かを探索する.
  • では、次のことが確認されました.
  • Aに基づいて、Bより大きい値
    • を決定する必要はない.
  • Bに基づいて、Aより大きい値
    • を決定する必要はない.
  • (いずれにしても組み合わせは、その総和がより大きくなるため、最適な組み合わせから遠ざかる)
    • .
  • そのため、次の追加ナビゲーションを実行します.
  • Aを基準としてBより小さい組み合わせに縮小し、
    • に移動する.
  • Bを基準としてAより小さい組み合わせに縮小し、
    • に移動する.
  • は、上記のナビゲーションを行うように構成することができる.
  • N個の数字を揃えなければなりません
  • A以上の値またはA未満の値は識別可能である.
  • B以下の値は、
  • Aはシーケンスではなく、組み合わせである.BがAより小さい場合、
    • のため、繰り返しナビゲーションが発生する.
  • は、[1,2,3,4,5,6,7]において、A,Bがそれぞれ3,4のとき、
  • 3+4>0.
  • 3を基準とすると、4未満の値[1,2](3,-1)をナビゲートする必要があり、(3,-2)は最終的には(-1,3)と(-2,3)と同じであるため、
    • を繰り返す可能性が高い.
  • 4に基づいて、3未満の値をナビゲートする必要があります[1,2](-1,4)(-2,4)
    • を繰り返す可能性もあります.
    ループを構成して
  • Aループを起点として、AとBをそれぞれ最小値と最大値に設定し、
    • に設定する.
  • ループのナビゲーション方向は
    • であり、AおよびBはそれぞれアレイの中央に収束する
    回答の提出

  • ループ不変性

  • 内容
  • Aが完了する.
  • Aが完了する.
  • Aである.

  • しょきじょうけん
  • Aは最小値であり、ナビゲーション可能なA
    • より小さくてはならない.
  • Bは最大値であり、ナビゲーション可能なB
    • より大きくはならない.

  • 維持条件
  • A+B=0の場合、最適な組み合わせナビゲーション
    • が完了する.
  • A+B<0の場合、Aを基準として「B格上」またはBを基準として「A格上」を検索すると、「B格上」は既に検索完了状態にあるため、「A格上」
    • を検索する.
  • A+B>0の場合、Aを基準として「B下段」または「A下段」を基準とすると、このとき「A下段」は既にナビゲーション完了状態にあるため、「B下段」はナビゲーション
    • となる.
  • のナビゲーション中に最適な組み合わせが見つかるたびに更新される場合、その組み合わせは、その時点までにナビゲートする最適な組み合わせ
    • である.

  • 終了条件
  • A>=B退出ループ
  • すべての組合せから最適な組合せへのナビゲーション完了
    • import sys
N = int(sys.stdin.readline())
values = list(map(int, sys.stdin.readline().split()))
values.sort()

a, b = 0, len(values)-1
optimal = (values[a], values[b], abs(values[a]+values[b]))
while values[a] < values[b]:
    A, B = values[a], values[b]    
    score = abs(A + B)
    if score < optimal[2]:
        optimal = (A, B, score)
    if A + B == 0:
        break
    elif A + B < 0:
        a += 1
    else:
        b -= 1
        
print(optimal[0], optimal[1])
    クリックして大きい図を見て、左右のスライドの切り替え、拡大・縮小のピクチャーを支持します
    Windows圧縮バックアップMySQLデータベース