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$。

题解

首先二分答案。

判定的时候，发现正着判很麻烦，考虑倒序。

那么就相当于，每轮操作为：

• 将每个 $h_i$ 修改为 $h_i - a_i$，这里需要保证 $h_i - a_i \ge 0$。
• $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $h_i + p$。
• 要求最终的 $h_{1 \dots n}$ 均不小于给定的 $n$ 个数。

那么可以考虑贪心：

• 每次选择最容易导致 $h_i - a_i < 0$ 的位置加上 $p$，如果选完了还是会导致则判定不合法。
• 如果不存在可能导致 $h_i - a_i < 0$ 的位置，则直接判定剩下的次数是否足够使最终的 $h_{1 \dots n}$ 均不小于给定的 $n$ 个数。

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

代码

const int N = 1e5 + 7;
int n, m, k, c[N];
ll h[N], a[N], p, l, r;

inline bool pd(ll o) {
	pq< pi > q;
	for (int i = 1; i <= n; i++) {
		if (h[i] + m * a[i] <= o) continue;
		q.push(mp(-(o / a[i]), i)), c[i] = 0;
	}
	int cnt = 0;
	for (int i = 1; q.size() && i <= m; i++)
		for (int j = 1; q.size() && j <= k; j++) {
			if (-q.top().fi < i) return 0;
			int x = q.top().se;
			q.pop();
			ll w = (o + (++c[x]) * p) / a[x];
			if (w < m) q.push(mp(-w, x));
			++cnt;
		}
	for (int i = 1; i <= n; i++) {
		ll w = o + c[i] * p - m * a[i];
		if (h[i] <= w) continue;
		w = (h[i] - w - 1) / p + 1;
		if (cnt + w > m * k) return 0;
		cnt += w;
	}
	return 1;
}

int main() {
	rd(n), rd(m), rd(k), rd(p);
	for (int i = 1; i <= n; i++)
		rd(h[i]), rd(a[i]),
		l = max(l, a[i]), r = max(r, h[i] + m * a[i]);
	while (l < r) {
		ll o = (l + r) >> 1;
		if (pd(o)) r = o;
		else l = o + 1;
	}
	print(l);
	return 0;
}