【基础】整体二分

namespace MultiBinarySearch {

static const int MAX_QUERY = 2e5 + 10;

struct Query {
    int id, cnt;    // 分cnt组时，每组的大小最大有多大？容易知道分的组数越多，其最大的siz会变小。
};

int ans[MAX_QUERY];

int check (int M) {
    int cnt = 0;
    // 实现这个根据M计算cnt的函数。通常复杂度为O(n)
    return cnt;
}

void multi_bs (int L, int R, const vector<Query> &vq) {
    if (vq.empty()) {
        // 一定要加这一句，否则如果check不是O(1)的，则复杂度不对
        return;
    }
    if (L == R) {
        for (auto &q : vq) {
            ans[q.id] = L;
        }
        // 注意处理无解的情况
        return;
    }
    int M = (L + R + 1) >> 1;
    int cnt = check (M);    // 当猜的答案为M时，最多能分cnt组
    vector<Query> vq1, vq2;
    for (auto &q : vq) {
        if (cnt >= q.cnt) {
            // cnt能满足q的要求，所以q至少为 M，对应 L = M
            vq1.push_back (q);
        } else {
            // cnt不能满足q的要求，所以q至多为 M - 1，对应 R = M - 1
            vq2.push_back (q);
        }
    }
    multi_bs (M, R, vq1);
    multi_bs (L, M - 1, vq2);
    return;
}

};

using namespace MultiBinarySearch;