Codeforces 1132D（二分模拟）

佚名 6年前 (2019-04-11) 随笔 1071人围观抢沙发百度已收录

要点

二分显然，关键在于怎么判断
题解方法：开k个队列代表每个时间有哪些电脑会挂掉，这部分O（n）预处理一下，之后扫一遍时间，每个时间点贪心选取最靠前的会挂的电脑未雨绸缪给它充电，然后看看充电以后要不要换队列，这样就把n * k的变成了n + k的

const int maxn = 2e5 + 5;
int n;
ll k;
ll a[maxn], b[maxn], cur[maxn];
queue<int>  Q[maxn];

bool ok(ll mid) {
    rep(i, 0, k)    while(Q[i].size())  Q[i].pop();
    rep(i, 1, n) {
        cur[i] = a[i];
        ll t = cur[i] / b[i] + 1;
        if (t <= k) Q[t].push(i);
        cur[i] %= b[i];
    }
    int p = 0;
    rep(i, 0, k) {
        while (p <= k && Q[p].empty())  p++;
        if (p > k)  return true;
        if (p <= i) return false;

        int t = Q[p].front();
        if (cur[t] + mid < b[t]) {
            cur[t] += mid;
            continue;
        }
        Q[p].pop();
        ll d = (cur[t] + mid) / b[t];
        if (p + d <= k) Q[p + d].push(t), cur[t] = (cur[t] + mid) % b[t];
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    k--;
    rep(i, 1, n)    cin >> a[i];
    rep(i, 1, n)    cin >> b[i];

    ll l = 0, r = INF, ans = -1;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (ok(mid)) {
            r = mid - 1;
            ans = mid;
        } else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}