My Blog

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$ <!-- more --> 要求最小化最大值，考虑二分一个最大的高度，将问题转化成可行性问题，即，给出一个高度，问能否使这些竹子最终不超过这个高度。

考虑限制这个问题不平凡的因素：因为每次降低竹子高度的时候不能保证竹子一定降低 p ，也就是说，“砸竹子”这一动作存在浪费。我们考虑尽可能的让“砸竹子”这一动作更少的浪费，即：尽可能在后面的时间点砸竹子，但是无法保证到底是在哪一次砸竹子，有可能已经结束了，没有形式化的计算流程。

可以考虑反向思考，即：假设已经长到 二分的高度。每次生长操作相当于每次会下落 $a_i$，而每次砸的操作相当于提升了 $p$ 的高度。

开始时，对每一个竹子计算出其需要多少次会下落到负高度，用堆维护，每次取出最快的可能下落到负高度的 k 个竹子，进行 “拔高” 操作。然后判断最后的高度是否大于等于$h_i$。

其实二分的本质是为了确定“尽可能的靠后砸竹子”的标准。反向思考是为了便于贪心处理策略。

code

{% note info CF505E Mr. Kitayuta vs. Bamboos %}

int n, m, k, p;
int H[_], A[_];
#define mp make_pair
#define fi first
#define se second
int height[_];
bool check(int MaxH){
    fill(height + 1, height + 1 + n, MaxH);
    priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > Q;
    while(!Q.empty()) Q.pop();
    for(int i = 1; i <= n; i++) if(MaxH - m * A[i] < H[i]) Q.push(mp( MaxH / A[i], i ));

    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= k; j++){
            if(Q.empty()) return true;
            pair<int, int> now = Q.top(); Q.pop(); 
            if(now.fi < i) return false;
            height[now.se] += p;
            now.fi = height[now.se] / A[now.se];
            if(height[now.se] - m * A[now.se] < H[now.se]) Q.push(now);
        }
    }
    return Q.empty();
}
signed main(){
    n = read(), m = read(), k = read(), p = read(); // 竹子数 天数 修改次数 最大降低高度 
    for(int i = 1; i <= n; i++) H[i] = read(), A[i] = read();

    int L = 0, ans = 0, R = 1LL << 60; for(int i = 1; i <= n; i++) L = min(L, A[i]);
    while(L < R){
        int mid = (L + R) >> 1;
        if(check(mid)) ans = mid, R = mid;
        else L = mid + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

{% endnote %}