mayoko’s diary

プロコンとかいろいろ。

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;
    }
};