TopCoder SRM 608 Div1 Easy MysticAndCandies
問題
n個の箱があり、i番目の箱には最小でlow[i]個、最大でhigh[i]個のキャンディーが入っている。
全ての箱に入っているキャンディーの数を合計するとCになることがわかっている。
いま、いくつかの箱を開けて、中に入っているキャンディーの個数の合計を、少なくともX個以上にしたい。
開けなければならない箱の個数の最小値はいくつか、求めよ。
制約条件
n≦50
low[i], high[i]≦1000万
解があることは保証されている
方針
開ける箱のlow[i]の和をa, high[i]の和をbとする。
a≧Xであったら自明にOK.
開けた箱が全部最小値だったとすると、残りのキャンディーC-a個が全て残りの箱に入っていなくてはならなくて、
残りの箱に入りきらなかった部分は開けた箱に入っていることになる。
すなわち、max(0, (C-a) - (M-b))個が開けた箱に余分に入っている。
(ただしMは全てのhighの和)
これを式にすると、a + (C-a) - (M-b)≧Xまたはa≧Xとなる
整理すると、
a≧Xまたはb≧X+M-Cであればよい。
前者の最適解はlowを大きい順に、後者の最適解はhighを大きい順に選んだものなので、
両方を試してサイズの小さいほうの解をとればいい。
ソースコード
class MysticAndCandies { public: int minBoxes(int C, int X, vector <int> low, vector <int> high) { int n = low.size(); int l = 0, h = 0; int goal = accumulate(all(high), 0) - C + X; sort(all(low)); sort(all(high)); rep(i, n){ l += low[n - 1 - i]; h += high[n - 1 - i]; if(l >= X || h >= goal) return i + 1; } assert(0); } };