菜王的 blog

出题人题解。

首先考虑一个最基本的策略：

假设我们要 check $p_k \ge X$ 是否合法。

那么我们只需要对于所有的 $1 \le l \le m, l \ne k$，分别令 $p_k = X, p_l = 1 - X$，其他的 $p$ 为 $0$，都 check 一次即可。

证明是显然的，如果我们要在 $p_k = X$ 的情况下分配其他的 $p$ 使得第 $i$ 个学生的加权总分超过第 $j$ 个学生的加权总分 $(a_{i, k} < a_{j, k})$，那么将剩下的 $1 - X$ 集中在 $a_{i, l} - a_{j, l}$ 最大的第 $l$ 个学科上一定不劣。

于是根据上述策略，我们得到了一个单组数据 $O(m^2 n \log n \log v)$ 并且需要二分的做法，但是答案需要输出有理数，无法二分。

考虑不排序而是直接暴力枚举 $i, j, k, l (a_{i, k} < a_{j, k}, a_{i, l} > a_{j, l})$，则我们得到一个不等式：

$X a_{i, k} + (1 - X) a_{i, l} \le X a_{j, k} + (1 - X) a_{j, l}$

解得：

$X \ge \frac{a_{i, l} - a_{j, l}}{a_{i, l} - a_{j, l} + a_{j, k} - a_{i, k}}$

于是题意就相当于对于每个 $k$，求上式的最大值，这个东西显然可以暴力 $O(n^2 m^2)$ 做。

$n \le 100$

发现需要最大化的分式是 $\frac p{p + q}$ 形式的，所以我们枚举 $i, j, l$ 确定 $p = a_{i, l} - a_{j, l}$ 并枚举 $k$ 最小化 $q = a_{j, k} - a_{i, k}$。

因为 $q$ 只与 $i, j, k$ 相关，并且 $k \ne l$，所以我们可以对每一对 $i, j$ 枚举 $k$ 来 $O(n^2m)$ 预处理出最小次小的 $q$，即可做到 $O(1)$ 查询 $q$。

于是我们得到了一个单组数据时间复杂度为 $O(n^2m)$ 的做法。

$m \le 100$

实际上，如果我们先枚举了 $k, l$，我们就不需要对所有的 $i, j$ 去判断了。根据比较的传递性，如果存在 $o$ 满足 $a_{i, k} < a_{o, k} < a_{j, k}$，则无需考虑 $i, j$ 这一对是否满足要求。于是我们对于某个 $(k, l)$，将 $a_{i, k}$ 相等的 $i$ 划为一类，则我们只需要考虑数值相邻的两个类。

考虑固定类别之后，$a_{i, k}, a_{j, k}$ 都被固定了，则 $\frac p{p + q}$ 中的 $q = a_{j, k} - a_{i, k}$ 已经被确定，则我们为了让分式最大，应该最大化 $p = a_{i, l} - a_{j, l}$，而 $p$ 是在两个类中各选取一个数作差，$a_{i, l}$ 选最大，$a_{j, l}$ 选最小即可。

每个点只会被一个类包含，对于每个类暴力扫一遍求出最大值与最小值，时间复杂度是 $O(n)$ 的。

于是我们又得到了一个单组数据时间复杂度为 $O(nm^2)$ 的做法。

结合一下

考虑数据分治，$n \le m$ 时跑 $O(n^2m)$，$n > m$ 时跑 $O(nm^2)$，则单组数据时间复杂度为 $O(nm\min(n, m))$。

设 $S = nm$，则 $\min(n, m) \le \sqrt S$。所以单组数据时间复杂度为 $O(S \sqrt S)$，可以通过本题。

另外，涉及到的分数分子和分母显然都不会超过 $2v = 2 \times 10^8$，不是 $998244353$ 的倍数，必定存在逆元。

关于分数比大小，因为分子分母都在 int 范围内，所以可以写一个 frac 类，比大小的时候开 long long 交叉相乘就不会有精度损失。

code