Visits: 303

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