E Revenge on My Boss CCPC 2023 Harbin Site 贪心，二分

传送门

给出了三个数组\(\{a_i\},\{b_i\},\{c_i\}\)要求给出一个排列\(p\)最小化：任选一个位置\(m\)，最大化贡献\(S=(\sum_{i=1}^ma_{p_i}+\sum_{i=m}^nb_{p_i})c_{p_m}\)。

标准的最小的最大提示我们考虑二分。

这里直接二分答案\(Mid\)。那么就考虑是否存在一个排列使得对于任意\(m=i\)都有\(S<=Mid\)

设\(d_i=a_i-b_i,B=\sum_{i=1}^nb_i\)

\(S=(\sum_{i=1}^md_{p_i}+B+b_{p_m})c_{p_m}\le Mid\)

\(\sum_{i=1}^m d_{p_i}\le Mid/c_{p_m}-B-b_{p_m}\)

右边只跟单点处的值有关，左边和排列有关。设\(lim_i=Mid/c_i-B-b_i\)

由此我们发现现将\(d_i\le 0\)的按照\(lim_i\)从大到小排序。

对于\(d_i>0\)的按照\(lim_i\)从小到大排序。由此\(check\)即可。