2015年6月29日月曜日

Code Festival : B - 枕決め

問題:

http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_d
m人の人がいる。それぞれの人は好みの枕の高さの範囲[xi,yi]が与えられる。
n個の枕がある。それぞれの枕の高さはh[i]で、これも与えられる。
枕は一人一つ使うものとして、最大で何人の人が枕を使うことが出来るか、人数を求めよ。

解法:

貪欲法で解ける。
まずは点と区間でソートする。
priority_queueを用意する(突っ込むものは区間で、ソート基準は右側の座標の小さい順)

点x[i]について、
1.その点を含むような区間をすべてpriority_queueに入れる。
2.priority_queueから区間を取り出し、もしそれがx[i]を含むものであったらx[i]はその区間とマッチング。そうでないならばpriority_queueから点を取り出し続ける。
3.マッチングの個数を出力

0 件のコメント:

コメントを投稿