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\)较大的优先，如果相同\(d_i\)较小的优先。
对于\(d_i>0\)的按照\(lim_i\)从小到大排序。由此\(check\)即可。