题解：P14174 【MX-X23-T4】卡常数

听取MLE声一片 · 2025-10-06 16:45:05 · 题解

先考虑每个数列内的情况。对于序列 i，选一个位置就是把这个数列的代价乘 \frac{a_{i,j}-b_{i,j}}{a_{i,j}}，把这些真分数排序，则一定从小到大选真分数最优。

计算出每个数列按照上述顺序选择每个数能让这个数列比选完上一个数减小的代价，称其为每个数的价值。不难发现在一个数列中价值是单调递减的。

那将所有数列所有数的价值放在一起排序，然后从大到小选择即可。

证明为一个数列内部选择数需要有顺序，而一个数列的价值单调递减，所以后续的数不可能先于前面的数进行选择，就能保证上述贪心正确。

设 m=\sum l_i，则时间复杂度 O(m\log m)。