[イーコタイ]配列-アンテナ

🔔 質問する

一直線上の村には何軒も家がある.特にアンテナを取り付けることにしました.効率を向上させるために,アンテナからすべての家屋までの総距離を最小限に抑えることを試みた.この場合、アンテナは、家屋の位置にのみ取り付けられ、論理的には、同じ位置に複数の家屋が存在することができる.家屋の位置値を指定する場合は、アンテナをインストールする場所を選択するプログラムを作成します.
例えば、N=4とし、各位置は1、5、7、9である.において、5の位置に取り付けられた場合、アンテナから全家屋までの距離の合計は(4+0+2+4)=10となり、最小となる.

入力

の最初の行では、家の数Nは自然数です.(1<=N<=200,000)

行目では、N棟の家の位置はスペースで区切られ、1万または10万以下の自然数で与えられています.

しゅつりょく

アンテナを第1行

に装着した位置の値を出力する.ただし、実装アンテナの位置値として複数の値を導出すると、最小値が出力される.

🎯 解答方法

この問題の核心思想は,アンテナが中間値に相当する家に取り付けられると,アンテナからすべての家までの距離の総和が最小になることである.中間値から外れた位置にアンテナを設置すると、アンテナからすべての家屋までの距離の合計が増加し続けます.したがって,この問題はすべての家の位置情報を入力して並べ替え,中間値を出力するだけで正確な判定が得られる.

💻 python code

n = int(input())
house = sorted(list(map(int, input().split())))

print(house[(n-1)//2]) # 중앙값