「CF506C」Mr. Kitayuta vs. Bamboos

发表于 分类于

$Link$

有 $n$ 棵竹子，每棵有一个初始高度 $h_i$ 和生长速度 $a_i$，每天 $n$ 棵竹子都会分别生长 $a_i$ 高度。

你可以把某一棵竹子砍下 $p$ 高度（如果竹子高度不足 $p$ 则砍到 $0$），这个操作每天可以最多做 $k$ 次。

问 $m$ 天后，最高的竹子的高度的最小值。

$1\le n\le10^5,1\le m\le5000,1\le k\le 10,1\le h_i,a_i\le10^9$。

首先显然是二分答案。

考虑怎么样砍最优，但是发现竹子高度不足 $p$ 这个点很恶心。

使用妙妙转化，我们把砍改成长，变为竹子每天变低 $a_i$，一次把竹子变高 $p$，注意我们只需要保证 $m$ 天后竹子的高度大于等于 $h_i$ 即可（否则说明无法达到最终的高度），避免了竹子高度不足 $p$ 的点。

考虑如何砍，我们处理出每棵竹子能否坚持 $m$ 天，若不能，则处理出在第几天无法坚持并丢进小根堆里，显然要优先处理更早坚持不了的竹子。如果堆顶能坚持的天数已经大于为了满足之前的操作，现在所在的天数，那就不合法了。否则把竹子高度增加 $p$，并重新计算能够支持的天数再丢进堆里。

具体实现时，可以先保证竹子高度非负，然后再最后把竹子的高度补齐到 $h_i$ 以上。

时间复杂度 $O((n+km)\log n\log w)$，其中 $w$ 为答案的值域，$w=\operatorname {max}(ma_i+h_i)\le5001\times10^9$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define ll long long
#define mid ((l + r) >> 1)
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;

int n, m, k, p;
int h[N + 1], a[N + 1];
ll per[N + 1];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
ll ans;

inline bool check(ll val)
{
    while (!q.empty())
        q.pop();
    for (int i = 1; i <= n; i++) {
        per[i] = val;
        if (per[i] - 1ll * m * a[i] < 0)
            q.push(make_pair(per[i] / a[i], i));
    }
    int cnt = 0;

    while (!q.empty() && cnt <= k * m) {
        ll days = q.top().first;
        int id = q.top().second;
        pair<ll, int> s = q.top();
        q.pop();
        int day = cnt / k + 1;
        if (days < day)
            return false;
        per[id] += p;
        cnt++;
        if (per[id] - 1ll * m * a[id] < 0)
            q.push(make_pair(per[id] / a[id], id));
    }
    if (cnt > k * m)
        return false;
    for (int i = 1; i <= n; i++) {
        if (per[i] - 1ll * m * a[i] >= h[i])
            continue;
        ll w = h[i] - (per[i] - 1ll * m * a[i]), sum = w / p + (w % p != 0);
        cnt += sum;
        if (cnt > k * m)
            return false;
    }
    return true;
}
int main()
{
    n = read();
    m = read();
    k = read();
    p = read();
    for (int i = 1; i <= n; i++) {
        h[i] = read();
        a[i] = read();
    }

    ll l = 0, r = 6e12;

    while (l <= r) {
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    printf("%lld\n", ans);
    return 0;
}