mayoko’s diary

プロコンとかいろいろ。

SRM 669 div1 easy:SubdividedSlimes

解法

とーらすさんが完全に解説してるのでそれを参考に。torus711.hatenablog.com

解説見るとわかるように priority_queue とやっているところは単に queue で良いですね。

int S, M;
 
bool ok(int x) {
    priority_queue<int> que;
    int num = S%(x+1);
    for (int i = 0; i < num; i++) que.push(-(S/(x+1)+1));
    for (int j = 0; j < x+1-num; j++) que.push(-S/(x+1));
    int sum = 0;
    while (que.size() > 1) {
        int p = -que.top(); que.pop();
        int q = -que.top(); que.pop();
        sum += p*q;
        que.push(-(p+q));
    }
    return sum >= M;
}
 
class SubdividedSlimes {
public:
    int needCut(int S, int M) {
        if (S*(S-1)/2 < M) return -1;
        ::S = S, ::M = M;
        int low = -1, high = S-1;
        while (high - low > 1) {
            int med = (high+low)/2;
            if (ok(med)) high = med;
            else low = med;
        }
        return high;
    }
};