[题解] CF505E Mr. Kitayuta vs. Bamboos

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 \cdots n}\) 中的最大值。
\(n \le 10^5\)，\(m \le 5 \times 10^3\)，\(k \le 10\)。

二分答案，考虑如何 check。

正着做要考虑对 0 取 max，比较麻烦，所以可以时光倒流。然后问题就变成了初始有 \(n\) 个数，每个都是 \(mid\)，每个时刻第 \(i\) 个会减少 \(a_i\)，你每个时刻可以进行 \(k\) 次操作，每次操作是选一个数让他加 \(p\)，求能不能在 \(m\) 个时刻后让每个数都大于等于 \(h_i\)，还要保证每个时刻数都非负。

这个可以贪心地去做，按还剩多少天减成负数维护一个堆，然后每次取出堆顶，对他操作一次，最后判断堆是否为空就行。

时间复杂度 \(O((n + mk) \log n\)。

constexpr int MAXN = 1e5 + 9, MAXM = 5e3 + 9, MAXK = 11;
int n, m, k, p, h[MAXN], a[MAXN], cnt[MAXN];

bool check(ll x) {
	priority_queue<pli, vector<pli>, greater<pli> > q;
	for (int i = 1; i <= n; i ++) {
		if (x - 1ll * m * a[i] >= h[i]) continue;
		q.emplace(x / a[i], i), cnt[i] = 0;
	}
	for (int i = 1; i <= m; i ++)
		for (int j = 1; j <= k; j ++) {
			if (q.empty()) return true;
			auto [day, id] = q.top(); q.pop();
			if (day < i) return false; cnt[id] ++;
			day = (x + 1ll * p * cnt[id]) / a[id];
			if (x - 1ll * a[id] * m + 1ll * p * cnt[id] < h[id])
				q.emplace(day, id);
		}
	if (q.size()) return false;
	else return true;
}

void slv() {
	n = Read<int>(), m = Read<int>(), k = Read<int>(), p = Read<int>();
	for (int i = 1; i <= n; i ++) h[i] = Read<int>(), a[i] = Read<int>();
	ll l = 0, r = 1e13;
	while (l < r) {
		ll mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	Write(l, '\n');
	return;
}