典型90

典型90 014 – We Used to Sing a Song Together(★3)

はじめに

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色!

今のレートは茶色です。

問題

典型90 014 - We Used to Sing a Song Together(★3)を解きました。

考察

全員が別々の学校に向かうときの不便さの最小値を求める問題。

ここで、不便さはそれぞれの子供の家から学校までの距離の総和であるため、それぞれの子供に別々の学校を選ばせたときの、距離の総和の最小値を求めればよい。

全探索の場合は計算量がO(N^2)になるため、実行時間に間に合わない。

ここで、距離の総和の最小値を取るには、それぞれの子供の家から最も近く、選択可能な学校を順に選び取っていけばいい。

子供の家から最も近い学校の選び方については、それぞれ昇順にソートしたもの(0から近い順)で貪欲的に求めることができます。

コード

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

A.sort()
B.sort()

ans = 0
bc = 0

for a in A:
    ans += abs(a - B[bc])
    bc += 1

print(ans)

まとめ

★3 レベルまでなら何とか瞬殺できますね。

★4 以上のレベルもサクッと解けるようになりたい。

COMMENT

メールアドレスが公開されることはありません。