蟻本の練習問題埋め2-2(1)

蟻本

貪欲法（区間）

POJ 2376 - Cleaning Shifts

http://poj.org/problem?id=2376

問題

N匹の牛がいて入れるシフトの区間が与えられる。
T個のシフトを全て埋めるために雇うべき牛の最小数を求めよ。

制約

N <= 25000
T <= 1000000

解法

KUPC2012のD権力の制約がきつい版。
開始時間でソートする。
今まで埋められていないシフトの中で一番早いシフトを埋めていく。
そのようなシフトを埋められる牛のうち、最も沢山のシフトを埋められる牛を選ぶ。
これを繰り返す。

POJ 1328 - Radar Installation

http://poj.org/problem?id=1328

問題

n個の点がある。
x軸上に点をいくつか取って、n個の点全てがx軸上に取った点を中心とした半径dの円に含まれるようにする。
このときx軸上に取るべき点の最小数を求めよ。
無理なら-1。

制約

n <= 1000

解法

y座標の絶対値がdより大きいものがあれば無理。
全ての点に対して、その点が円周上に来るような円のx座標を求める（2つあるが、右側で良い）。
そのような円を左から調べ、対応する点にフラグが立っていなければその円を使い、その円で被覆できる点全てにフラグをたてる。
これを繰り返す。

POJ 3190 - Stall Reservations

http://poj.org/problem?id=3190

問題

N匹の牛がいて、それぞれ乳絞りされる時間の区間[A,B]が決まっている。
乳絞りは牛舎で行われ、１つの牛舎には1匹まで牛が入る。
全ての牛の乳絞りを決められた時間に牛舎で行いたい。
そのために必要な牛舎の最小数と、その最小数を実現するための牛の牛舎への割り当て方を求めよ。

制約

N<=50000
A,B<=10^6

解法

各区間について、inとoutのイベントを作り、時間でソートする。
inのとき、キュー(スタックでも何でもいい)に空いている牛舎が入っていれば、その牛舎を割り当てる。
空いている牛舎がキューに入っていなければ、牛舎を増やし、増やした牛舎を割り当てる。
outのとき、割り当てられていた牛舎をキューに入れる。
というふうにして解く。