题目大意
有 $n$ 次考试,第 $i$ 次的满分为 $b_i$,你的得分为 $a_i$,你可以删去 $d$ 次考试,从而你最后的分数为剩下的得分与剩下的总分之比,现存在一种方案,即删去 $\dfrac{a_i}{b_i}$ 最小的 $d$ 次考试,你可以任意删去 $d$ 个考试,求所有的 $d$,使得存在一个最后分数更高的方案。
$n\le 5\times 10^4$。
思路
显然可以对所有考试排序预处理出每个 $d$ 的原始方案所得分数 $\dfrac{S_d}{T_d}$。
考虑暴力,如果一个 $d$ 合法,则可以找到 $n-d$ 次考试,使得 $\dfrac{\sum a_{p_i}}{\sum b_{p_i}}>\dfrac{S_d}{T_d}$,其中 $p$ 表示一个方案的的下标集合。
问题转化为求 $\max\left\{\dfrac{\sum a_{p_i}}{\sum b_{p_i}}\right\}$,可以用 0/1 分数规划 + 0/1 背包在 $O(n^2\log n)$ 的时间复杂度下解决。
更进一步,如果一个 $d$ 合法,则可以在原始方案中替换一个 $i$ 变为 $j$,其中 $i\le d < j\le n$,使得方案更优,即 $\dfrac{S_d-a_i+a_j}{T_d-a_i+a_j}>\dfrac{S_d}{T_d}$,化简得 $b_iS_d-a_iT_d< b_jS_d-a_jT_d$,设
$$
f(d)=\min\{b_iS_d-a_iT_d\}(1\le i\le d)
$$
$$
g(d)=\max\{b_iS_d-a_iT_d\}(d< i\le n)
$$
则 $d$ 可以作为一个合法方案,当且仅当 $f(d)< g(d)$,可以 $O(n^2)$ 枚举解决。
考虑优化,发现这个式子很像斜率优化。
以 $f(d)$ 为例,原式可化为 $\dfrac{f(d)}{S_d}=\min\left\{b_i-\dfrac{T_d}{S_d}a_i\right\}$。
这里 $b=\dfrac{f(d)}{S_d}, y=b_i, k=\dfrac{T_d}{S_d}, x=a_i$。即 $b=\min\{y-kx\}$,可以维护一个下凸包,以保证决策最优。
与一般的斜率优化不同的是,这题的横坐标 $x$ 并不是递增的,即无法直接通过一般的数据结构(单调队列,单调栈)维护,这里通过 CDQ 分治维护。
在分治时维护凸包,先保证左半部分的横坐标 $x$ 递增(用归并排序保证时间复杂度),计算左半部分的凸包对右半部分的 $f(d)$ 的影响,不断向下递归即可解决问题。
最后,考虑 $k=\dfrac{T_d}{S_d}$ 的单调性。可以先证明 $\dfrac{b_1}{a_1}>\dfrac{b_1+b_2}{a_1+a_2}$(因为我们对考试进行了排序,即保证了 $\dfrac{a_i}{b_i}< \dfrac{a_j}{b_j}(i< j)$),然后用数学归纳法可以得出 $\dfrac{T_d}{S_d}$ 单调递减。根据斜率优化的基本操作,计算 $f$ 时用单调栈维护凸包,计算 $g$ 时用单调栈维护,即可在 $O(n\log n)$ 的时间复杂度下解决问题。
参考代码
1 | const int MAXN = 100000 + 5; |