ただのメモ

他の人に見せても良い方のメモ

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?(これは価値観が大きく影響しそう)
  • 二つの変数に対して、
    •  max(\Sigma y) satisfying   \Sigma x <C
    • という問題に行きつきそう。

 

Bye Bye!