SRM 456 div1 med, div2 hard: CutSticks
450pt だったけど確かにこれは簡単。
解法
二分探索でやります。
ok(x) = (C 回カットした後の K 番目の数が x 以上になるような切り方が存在するか) というチェック関数を作れればハッピーです。
sticks[i] が x を使って何分割できるかを考えると, div = sticks[i]/x として, div-1 個 x に分割して, 残った stick はそのまま, というように分割するのが一番効率が良いです。
このようにしてたかだか C 回のカットで x 以上の stick を作っていき, K 個以上作れるなら ok(x) は true, できないなら false を返すようにすれば良いです。
bool ok(double x, const vi& sticks, int C, int K) { ll num = 0, n = sticks.size(); for (int i = 0; i < n; i++) { ll plus = sticks[i]/x; plus = max<ll>(plus-1, 0); plus = min<ll>(plus, C); num += plus; double rest = sticks[i]-x*plus; if (rest >= x) num++; C -= plus; } return num >= K; } class CutSticks { public: double maxKth(vector <int> sticks, int C, int K) { double low = 1./1e10, high = 1e10; sort(sticks.begin(), sticks.end()); reverse(sticks.begin(), sticks.end()); for (int i = 0; i < 100; i++) { double med = (low+high)/2; if (ok(med, sticks, C, K)) low = med; else high = med; } return low; } };