Statement

有 $n$ 根竹子，第 $i$ 根初始时高度为 $h_i$ 。你需要依次进行如下操作 $m$ 轮：

重复 $k$ 次，从 $n$ 根竹子中选出一根，将它的高度减少 $p$ 。若当前 $h_i<p$ ，则将 $h_i$ 改为 $0$ 。
对于 $\forall i\in[1..n]$ ，将第 $i$ 根竹子的高度增加 $a_i$ 。

请你最小化所有操作结束时，最高的竹子的高度。

数据范围： $n\le10^5$ ， $m\le5000$ ， $k\le10$ 。

Solution

考虑二分答案后如何 check。不好做的是 $h_i$ 会改成 $\max\{h_i-p,0\}$ 。

尝试将整个函数向上平移，函数就变成了 $h_i+\Delta$ 出发到 $\text{mid}$ ，一路上 $h_i$ 均 $\ge0$ 。

因为最后时刻是确定的，因此倒序考虑，变成了『有 $n$ 根初始时高度为 $\text{mid}$ 的竹子，操作是选择 $k$ 根高度减少 $p$ ，然后所有竹子高度增加 $a_i$ ，问最后每根竹子高度 $\ge h_i$ 是否可行』。

拿一个堆，维护 $\text{mid}+p\cdot c_i-a_i\cdot m<h_i$ 的所有竹子中， $\left\lfloor\frac{\text{mid}+p\cdot c_i}{a_i}\right\rfloor$ 最小的竹子 $i$ 。其中 $c_i$ 表示竹子 $i$ 增高的次数。每次取出堆顶，判断堆顶是否已经 $<0$ ，以及最后堆是否为空。

时间复杂度 $O((n+mk)\log n\log V)$ ，其中 $V$ 是值域。

Code

#include <bits/stdc++.h>
template <class T, int S, class cmp = std::less<T>>
struct PriorityQueue {
    T q[S];
    int tail;
    PriorityQueue() { tail = 0; }
    void clear() { tail = 0; }
    bool empty() { return tail < 1; }
    int size() { return tail; }
    void push(T x) { q[tail++] = x, std::push_heap(q, q + tail, cmp()); }
    void pop() { std::pop_heap(q, q + tail, cmp()), tail--; }
    T top() { return q[0]; }
};
typedef long long LL;
typedef std::pair<LL, int> pli;
const int N = 1e5 + 7;
int n, m, k, p, h[N], a[N];
bool check(LL H) {
    static PriorityQueue<pli, N, std::greater<pli>> pq;
    static LL b[N];
    pq.clear();
    for (int i = 1; i <= n; i++) {
        b[i] = H;
        if (b[i] - (LL)a[i] * m < h[i]) pq.push({b[i] / a[i], i});
    }
    for (int day = 1; day <= m; day++)
        for (int tm = 1; tm <= k && !pq.empty(); tm++) {
            int x = pq.top().second;
            pq.pop();
            if (b[x] / a[x] < day) return 0;
            b[x] += p;
            if (b[x] - (LL)a[x] * m < h[x]) pq.push({b[x] / a[x], x});
        }
    return pq.empty();
}
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &p);
    for (int i = 1; i <= n; i++) scanf("%d%d", h + i, a + i);
    LL l = 0, r = 1e13, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return printf("%lld\n", l), 0;
}