問題

014 - We Used to Sing a Song Together（★3）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programmi

pythonコード

python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
min_incon = 0
for i in range(n):
    min_incon += abs(a[i] - b[i])

print(min_incon)

ポイント

• ソートする
• 貪欲法
  • このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。(wikipedia)