[白俊2230]寿司選び(Python)

4449 ワード
アルゴリズム#アルゴリズム# ピックアップ 白駿2230 python テキストリンク
1.アイデア
問題は,数列で2つの数を選択した場合,差がM以上で最小を求める場合である.2つの数を選択するには、数列の形式は重要ではありません.したがって,ソート後,問題タイプで提案したように,二重ポインタを用いて問題を解決する.注意が必要なのは、同じ数を選ぶ場合もあります.例えば、N=1の場合、2回の数字が選択される.整数を1つ選択して2回差を求める.すなわち、数列をアレイ(arr)として表す場合、左側ポインタ(lp)、右側ポインタ(rp)を同じインデックスに配置し、同じ位置を指す数の違いを考慮しなければならない.(もちろん、結果は0)
差がM以上であれば,事前に数列を並べ替えたので,rpが指す箇所は後で考慮しなくてもよい.私たちが求めているのはM以上の違いなので、最小の状況を求めます.したがってlpは次の数を示し,lpが示す箇所もrpを示す.
差がM未満の場合、rpは次の数を示す.差がM以上になるまで繰り返し、rpがNに達する瞬間、lpは次の数を示し、rpもlpが示す場所を示す.
lpがNに達するまで、以上の手順を繰り返します.そして差がM以上で、差が一番小さいものを選べばいいです.
2.コード
import sys

n, m = map(int, sys.stdin.readline().rsplit())
arr = []
for _ in range(n): arr.append(int(sys.stdin.readline().rstrip()))

arr.sort()
lp, rp = 0, 0
answer = int(2e9)

while lp < n:
    diff = abs(arr[lp]-arr[rp])
    if diff >= m:
        answer = min(answer, diff)
        if diff == m : break
        lp += 1
        rp = lp
        continue

    rp += 1
    if rp == n:
        lp += 1
        rp = lp

print(answer)
Baekjun-2304号(倉庫ポリゴン)
03.制御文-条件文