Codeforces Round #339 (Div. 1) B. Skills

問題文

codeforces.com

問題概要

現在のプレイヤーの各スキルレベルは a1, a2, ... , an である。 いま、スキルレベルを 1 上げるアイテムを m 個持っている。 アイテムをいくつか使ってプレイヤーの力を最大化したい。 ただし、スキルレベルには上限値 A が存在し、スキルレベルは A 以上にすることはできない。

なお、プレイヤーの力は次のように定義される。

  • (上限値に達したスキルの種類数) cf +(スキルレベルの最小値)cm

解法

上限値まで引き上げるスキル数を決め打ってから、可能なスキルレベルの最小値を二分探索すればいい。

まずソートしておく。上限に引き上げる対象は大きい値のほうがいいので右側から埋める。

最小値を Min と仮定したとき、最小値を Min にするのに必要なアイテム数は図の緑色の領域の面積に相当する。 Min 以上になる最小のインデックスを求めるのはlowerbound で O(log n)、面積は累積和を使って O(1) で求められる。

f:id:pekempey:20160115185648p:plain

Codeforces Round #339 (Div. 1) B. Skills

バグらせてしまい辛かった。実装力が欲しい。