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 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...