题解 CF1765J【Hero to Zero】
周子衡
·
·
题解
注意到操作的顺序无关紧要。我们可以把所有行上的操作合并，变成给第 i 行减去某个值 x_i，需要付出 x_i 的代价；所有列上的操作合并，变成给第 j 行减去某个值 y_j，需要付出 y_j 的代价。需要满足
x_i+y_j\leq c_{i,j},\forall i,j\in[1,n]
需要付出的总代价为
\sum_{i=1}^nx_i+\sum_{j=1}^ny_j+\sum_{i=1}^n\sum_{j=1}^n(c_{i,j}-x_i-y_j)=(\sum c_{i,j})-(n-1)(\sum x_i+\sum y_j)
我们希望总代价尽可能小，也就是 \sum x_i+\sum y_j 尽可能大。线性规划中的一个经典结论告诉我们，这个最大值是
\sum_{i=1}^nc_{i,p_i}
的最小值，其中 (p_1,...,p_n) 取遍 (1,...,n) 的所有排列。
由于 c_{i,j}=|a_i-b_j|，假设 a,b 都是升序的，最小的一组排列显然就是 p_i=i。计算 \sum c_{i,j} 也非常简单。总时间复杂度 O(n\log n)。