CF505E Mr. Kitayuta vs. Bamboos 题解

作者: xht37 分类: 题解 发布时间: 2019-12-04 15:33

Visits: 265

CF505E Mr. Kitayuta vs. Bamboos

题意

  • 给定 $n$ 个数 $h_{1 \dots n}$。
  • 你需要进行 $m$ 轮操作,每轮操作为 $k$ 次修改,每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i – p, 0)$。
  • 每轮操作后每个 $h_i$ 将会被修改为 $h_i + a_i$。
  • 你需要最小化最终 $h_{1 \dots n}$ 中的最大值。
  • $n \le 10^5$,$m \le 5 \times 10^3$,$k \le 10$。

题解

首先二分答案。

判定的时候,发现正着判很麻烦,考虑倒序。

那么就相当于,每轮操作为:

  • 将每个 $h_i$ 修改为 $h_i – a_i$,这里需要保证 $h_i – a_i \ge 0$。
  • $k$ 次修改,每次修改可以选择一个数 $h_i$ 修改为 $h_i + p$。
  • 要求最终的 $h_{1 \dots n}$ 均不小于给定的 $n$ 个数。

那么可以考虑贪心:

  • 每次选择最容易导致 $h_i – a_i < 0$ 的位置加上 $p$,如果选完了还是会导致则判定不合法。
  • 如果不存在可能导致 $h_i – a_i < 0$ 的位置,则直接判定剩下的次数是否足够使最终的 $h_{1 \dots n}$ 均不小于给定的 $n$ 个数。

时间复杂度 $\mathcal O((n + mk) \log n \log w)$。

代码

const int N = 1e5 + 7;
int n, m, k, c[N];
ll h[N], a[N], p, l, r;

inline bool pd(ll o) {
    pq< pi > q;
    for (int i = 1; i <= n; i++) {
        if (h[i] + m * a[i] <= o) continue;
        q.push(mp(-(o / a[i]), i)), c[i] = 0;
    }
    int cnt = 0;
    for (int i = 1; q.size() && i <= m; i++)
        for (int j = 1; q.size() && j <= k; j++) {
            if (-q.top().fi < i) return 0;
            int x = q.top().se;
            q.pop();
            ll w = (o + (++c[x]) * p) / a[x];
            if (w < m) q.push(mp(-w, x));
            ++cnt;
        }
    for (int i = 1; i <= n; i++) {
        ll w = o + c[i] * p - m * a[i];
        if (h[i] <= w) continue;
        w = (h[i] - w - 1) / p + 1;
        if (cnt + w > m * k) return 0;
        cnt += w;
    }
    return 1;
}

int main() {
    rd(n), rd(m), rd(k), rd(p);
    for (int i = 1; i <= n; i++)
        rd(h[i]), rd(a[i]),
        l = max(l, a[i]), r = max(r, h[i] + m * a[i]);
    while (l < r) {
        ll o = (l + r) >> 1;
        if (pd(o)) r = o;
        else l = o + 1;
    }
    print(l);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注