题解 CF505E 【Mr. Kitayuta vs. Bamboos】

[My Blog](https://shuyumo2003.github.io/2020/%E3%80%8C%E9%A2%98%E5%8D%95%E3%80%8DIOI2020%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E4%BD%9C%E4%B8%9A-Part-1/#CF505E-Mr-Kitayuta-vs-Bamboos) # 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 %} ```cpp 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 %}