CF446B DZY Loves Modification(CF446B DZY Loves Modification)

题面:CF446B DZY Loves Modification

题意:

\(zyb\) 有一个 \(n \times m\) 的矩阵,他每次选某一行或者某一列,使自己的快乐值加上这一 行/列 的总和。之后这一 行/列 的所有数字大小减去 \(p\) 。问 \(k\) 次操作之后最大快乐值为多少。

解法:

由于某一行的更改不会影响其他行的答案,某一列的更改不会影响其他列的答案,所以我们单独考虑行和列。

令 \(sum_1[i]\) 表示单独操作行 \(i\) 次能得到的最大快乐值,\(sum_2[i]\) 表示单独操作列 \(i\) 次能得到地最大快乐值。所以答案就是 \(\max\) {\(sum_1[i] + sum_2[k-i]+p \cdot i \cdot(k-i)\)}。

预处理 \(sum_1\) 和 \(sum_2\) 两个数组就用优先队列,不多解释。

至于减 \(p \cdot i \cdot(k-i)\) ,可以考虑成 \(i\) 条行线和 \((k – i)\) 条列线的交点个数。(这个手玩小样例也能发现)

时间复杂度:

\(O(k \log n)\) 。

Code

————————

题面:CF446B DZY Loves Modification

< strong > meaning of the question: < / strong >

\(ZYB \) has a \ (n \ times m \) matrix. Each time he selects a row or column, he adds his happiness value to the sum of this row / column. After that, subtract \ (P \) from the size of all numbers in this row / column. Ask the maximum happiness value after \ (K \) operations.

< strong > solution: < / strong >

Since the change of one row will not affect the answers of other rows and the change of one column will not affect the answers of other columns, we consider rows and columns separately.

Let \ (sum_1 [i] \) represent the maximum happiness value that can be obtained by a single operation line \ (I \) times, and \ (sum_2 [i] \) represent the maximum happiness value that can be obtained by a single operation column \ (I \) times. So the answer is \ (\ Max \) {\ (sum_1 [i] + sum_2 [k-i] + P \ cdot I \ cdot (k-i) \)}.

The two pre-processing arrays \ (sum_1 \) and \ (sum_2 \) use priority queues. I won’t explain more.

As for subtraction \ (P \ cdot I \ cdot (k-i) \), it can be considered as the number of intersections of \ (I \) row lines and \ ((k – I) \) column lines. (this hand play sample can also be found)

< strong > time complexity: < / strong >

\(O(k \log n)\) 。

Code