CF626G Raffles 题解

CF626G Raffles

题意

• 有 $n$ 个奖池，第 $i$ 个奖池的奖金是 $p_i$，已经有 $l_i$ 张彩票押在上面。
• 现在你有 $t$ 张彩票，你需要将你的彩票分配到这些奖池中，并且保证你在每个奖池中押的彩票数不能超过该奖池原有的彩票数。
• 若你在第 $i$ 个奖池中押了 $t_i$ 张彩票，则你中奖的概率为 $\frac{t_i}{t_i + l_i}$，若你中奖，你可以获得这个奖池的全部奖金 $p_i$。
• 一共有 $q$ 次事件，每次事件会使某个 $l_i$ 加 $1$ 或减 $1$。
• 你需要在每个事件后求出在最佳方案下你获得的奖金总数的最大期望值。
• $n,t,q \le 2 \times 10^5$，$p_i,l_i \le 10^3$，答案精度误差 $\le 10^{-6}$。

题解

首先考虑没有修改时如何计算。

假设此时对于奖池 $i$，你已经押了 $c_i$ 张彩票上去了，若 $c_i + 1 \le l_i$，则你此时还可以再押一张彩票上去，它对答案的贡献为

$$p_i(\frac{c_i+1}{c_i+1+l_i} - \frac{c_i}{c_i+l_i}) = \frac{p_il_i}{(c_i+1+l_i)(c_i+l_i)}$$

注意到这个贡献随着 $c_i$ 的增大会不断变小，因此我们可以得到一个贪心做法：

开一个堆存储对于每个奖池再押一张彩票的贡献，每次取出最大的贡献计入答案，然后加入其对应奖池的新的贡献。

时间复杂度为 $\mathcal O((n + t) \log n)$。

再考虑有修改的情况下如何维护。

当我们修改 $l_i$ 时，第 $i$ 个奖池的贡献会改变，因此当前方案可能就不是最优的了。

一个简单的想法是，如果当前的方案不是最优的方案，那么就不断找回当前方案中贡献最小的彩票，换成贡献更大的彩票。

可以发现，这个看似暴力的做法时间复杂度却是对的，因为每次修改实质上只会最多引起一张彩票的变化。

具体实现上，我们只需要把堆换成 multiset，同时维护当前方案即可。

总时间复杂度 $\mathcal O((n + t + q) \log n)$。

代码

const int N = 2e5 + 7;
const ld inf = 1e18L, eps = 1e-10L;
int n, t, q, p[N], l[N], c[N];
ld ans;

inline ld f(int x, int c) {
	if (!~c) return inf;
	if (c >= l[x]) return 0L;
	return 1.0L * p[x] * l[x] / (c + 1 + l[x]) / (c + l[x]);
}

inline ld g(int x) {
	return 1.0L * p[x] * min(c[x], l[x]) / (min(c[x], l[x]) + l[x]);
}

struct P {
	ld o;
	int x, c;
	inline P(int x = 0, int c = -1) : x(x), c(c) { o = f(x, c); }
	inline bool operator < (const P w) const {
		return abs(o - w.o) > eps ? o < w.o : x < w.x;
	}
};
multiset<P> s, e;

inline void add() {
	auto it = --s.end();
	ans += it -> o;
	int x = it -> x;
	e.erase(P(x, c[x] - 1)), e.insert(*it);
	s.erase(it), s.insert(P(x, ++c[x]));
}

inline void rmv() {
	auto it = e.begin();
	ans -= it -> o;
	int x = it -> x;
	s.erase(P(x, c[x])), s.insert(*it);
	e.erase(it), e.insert(P(x, (--c[x]) - 1));
}

int main() {
	rd(n), rd(t), rd(q);
	for (int i = 1; i <= n; i++) rd(p[i]);
	for (int i = 1; i <= n; i++) rd(l[i]), s.insert(P(i, 0)), e.insert(P(i));
	while (t--) add();
	for (int i = 1, o, x; i <= q; i++) {
		rd(o), rd(x);
		s.erase(P(x, c[x])), e.erase(P(x, c[x] - 1)), ans -= g(x);
		l[x] += o == 1 ? 1 : -1;
		s.insert(P(x, c[x])), e.insert(P(x, c[x] - 1)), ans += g(x);
		while ((--s.end()) -> o > (e.begin() -> o) + eps) rmv(), add();
		printf("%.10Lf\n", ans);
	}
	return 0;
}