Competitive Programing Typical 90 Problem day14

Day 14.

So easy problem.

As you know, Greedy Strategy is versatile in everyday life.

This problem is just one example.

Code is below.

N = int(input())

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

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

A.sort()

B.sort()

answer = 0

for i in range(N):

  answer+= abs(A[i]-B[i])

print(answer)

• あまりにもあっけなく解けたので、もう少し書く。
• 貪欲法について。こちら。
  • 貪欲法の操作は以下の通り。
    • 問題を複数の部分にバラバラにする。
      • 重なりは無いとする
    • バラバラにしたものから、何とかして評価値を取り出す
      • 順序のつくものなら何でもよい
    • その評価値の高いものから、処理していく。
      • 評価値の高いもの
        • 金額の高い
        • 高価なものから手を出すので、欲深い
          • 「貪欲」の由来 
      • 一度処理したら、捨てる。
        • 使い捨て
          • カイロ
        • 消耗品
      • 状態は1つで良い
        • 動的計画法との違い
        • これが、最適解に行きつかないことがあることに繋がる。
• 貪欲にしたために、うまく行かないことはあるかしら。
  • 入試問題
    • 得点の高い問題から解いていくと、時間が足りなくなる
    • むしろ、小さな典型問題から解いていく方が総得点が上回る
  • 病院
    • 病態の悪い患者から救いたいが、一人当たりの治療時間・労力が大きい
    • むしろ、軽症の人から治療する方が、Better？（これは価値観が大きく影響しそう）
• 二つの変数に対して、
  • satisfying
  • という問題に行きつきそう。

Bye Bye！