CF1607H 题解

GaryH · 2021-11-15 17:15:00 · 题解

CF1607H 题解

Nov/18/2021. Upd:修改了一个笔误

Nov/25/2021. Upd:修改了第二个笔误

题意：给 n 个二元组和一个数组 m[1...n]，第 i 个二元组形如 (a_i, b_i)。

需要你构造出 n 个新的二元组，要求是：

第 i 个新二元组 (a'_i, b'_i) 需要满足以下条件：a'_i \leq a_i, b'_i \leq b_i, a'_i + b'_i = a_i + b_i - m_i。

请最小化新的 n 个二元组中的本质不同二元组个数并给出方案，

其中两个二元组 (a, b) , (c, d) 本质不同，当且仅当 a \neq c 或 b \neq d。

做法：

首先，我们定义 val_i = a_i + b_i - m_i，则有 val_i = a'_i + b'_i，

故若 val_i \neq val_j，则 (a'_i,b'_i) 与 (a'_j, b'_j) 必然本质不同。

那么，我们将原来的 n 个二元组按 val 值分类后，不同类的两个元素必本质不同，

而对于属于同一类的两个二元组 (a_i, b_i), (a_j, b_j)，想要使这两者对应的新二元组本质相同，

我们只需要让 a'_i = a'_j 即可， 因为若 val_i = val_j，则 a'_i + b'_i = a'_j + b'_j。

我们同时可以发现，对某个二元组 (a_i, b_i)，由它构造出的新二元组 (a'_i, b'_i) 必满足以下条件：

• a'_i \leq a_i
• a'_i \leq val_i
• a'_i \geq 0
• a'_i \geq a'_i - m_i
• a'_i + b'_i = val_i

以上五个条件是构造出的新二元组 (a'_i, b'_i) 合法的充要条件。

我们将上面五个条件合并，即可得出：