競プロ典型 90 問：070 - Plant Planning（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_br

挑戦結果

• 挑戦日：2021/10/29
• 結果：解けた
• 時間：10分

考えたこと

• X方向とY方向は独立して考えてOK。
• 発電所の左右にある工場数が同じあれば効率が良い。
• 工場の座標をソートして、中央にある部分に発電所を作ればOK

公式解説

https://twitter.com/e869120/status/1406020809492090882

解説を読んだふりかえり

• 珍しく、考察も実装もするっといった。
• 中央値で絶対値最小となるテクニックは重要らしい。

ソース

N = int(input())
X,Y = [],[]
for _ in range(N):
    x,y = [int(x) for x in input().split()]
    X.append(x)
    Y.append(y)

# XとYについては、独立して考えてOK。
# 発電所の左側と右側の工場の数が等しい場合が最短になる
# ソートして真ん中にある工場の場所を採用すればOK
X.sort()
Y.sort()
m = N//2
# 発電所の場所はX[m],Y[m]。そこからの距離を求める
XX = [abs(X[i] - X[m]) for i in range(N)]
YY = [abs(Y[i] - Y[m]) for i in range(N)]
ans = sum(XX) + sum(YY)
print(ans)