自动搬运

查看原文

来自洛谷，原作者为

	xzCyanBrad 韬光养晦 决不当头 有所作为

搬运于2025-08-24 22:29:48，当前版本为作者最后更新于2024-07-16 23:12:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一个不用凸包的非常容易的题解。

先对题目中的式子进行一个转化。

$$\begin{aligned} &\max_{S\subseteq [N],|S|=R}\left(\min_{A,D\in\Z^+}\dfrac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\right)\ge x\\ \Leftrightarrow&\exist S\subseteq [N]\land|S|=R,\forall A,D\in\Z^+,\dfrac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\ge x\\ \Leftrightarrow&\exist S\subseteq [N]\land|S|=R,\forall A,D\in\Z^+,\exist i\in S,A\times d_i+D\times a_i\ge x\left(\max_{j\in [N]}(A\times d_j+D\times a_j)\right)\\ \Leftrightarrow&\exist S\subseteq [N]\land|S|=R,\forall A'\in\R^+,\exist i\in S,A'\times d_i+a_i\ge \max_{j\in [N]}(xA'\times d_j+xa_j)\\ \color{red}\textbf{(!): }\color{CandyBar}\Leftrightarrow&\exist S\subseteq [N]\land|S|\le R,\forall A'\in\R^+,\exist i\in S,\forall j\in [N],A'\times d_i+a_i\ge xA'\times d_j+xa_j\\ \end{aligned} $$

考虑枚举所有的 $(i,j)$，怎么拓展？发现最后一式，当 $(i,j)$ 固定时，$A'$ 不是在 $[v,+\infty)$ 内，就是在 $(0,v]$ 内，取决于 $v=d_i-xd_j$ 的符号。

考虑对于每个 $i$，得到这个 $A'$ 的范围，最后做一个 dp，因为左端点是 $0$，右端点直接看在 $r$ 个内能否覆盖到 $+\infty$ 就行了。

注意特判 $d_i-xd_j=0$ 的情况。

复杂度 $\Theta(Tn^2\log V)$，跑了 $3.38s$。