白俊回答-2230回選択

📜 理解问题

N個の整数からなる数列A[1],A[2],...,A[N]がある.この数列で2つの数(同じ数かもしれません)を選択する場合は、Mよりも差が大きく、最小のプログラムを作成します.
たとえば、カラム{1,2,3,4,5}を数えます.M=3の場合、1 4、1 5、2 5を選択した場合、その差はMより大きい.ここで最も差が少ないのは、1 4または2 5を選択したときの3です.

💡 問題の再定義

出力がMより大きく、最小の差.

▼▼▼計画作成

まず入力をソートします.並べ替えの理由は、二重ポインタを使用するために、整列したデータを使用する必要があるからです.

ソートに成功した場合は、startインデックスとendインデックスの和がMより大きいかどうかをダブルポインタで確認し、Mより大きい場合はstartを増やし、最小の差を決定してmindifferenceを更新します.Mより小さい場合はendを増やして次の入力との和を求める.以上の手順はstartもendもNになるまで繰り返される.

この場合、startとendのインデックスの差が大きいほど値の差が大きくなり、インデックスの差が小さいほど値の差が小さくなるため、ダブルポインタでソートできます.

💻 計画の実行

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    nums = []
    min_difference = float("inf")
    for i in range(N):
        nums.append(int(sys.stdin.readline().rstrip()))

    nums.sort()
    start = 0
    end = 1

    while start < end:
        difference = nums[end] - nums[start]
        if difference >= M:
            if min_difference > difference:
                min_difference = difference
            start += 1
            if start == end and end != N - 1:
                end += 1
        else:
            if end == N - 1:
                start += 1
            else:
                end += 1

    print(min_difference)

🤔 振り返る

これは,ソートと二重ポインタを用いると,部分的なマージ問題でなくても利用できることを意識した問題である.